Search results for: cubic graphs

Authors: Bin Sheng, Changhong Lu

Abstract:

Let G be a simple undirected graph with no isolated vertex. A paired dominating set of G is a dominating set which induces a subgraph that has a perfect matching. The paired domination number of G, denoted by γₚᵣ(G), is the size of its smallest paired dominating set. Goddard and Henning conjectured that γₚᵣ(G) ≤ 4n/7 holds for every graph G with δ(G) ≥ 3, except the Petersen Graph. In this paper, we prove this conjecture for cubic graphs.

Keywords: paired dominating set, upper bound, cubic graphs, weight function

Procedia PDF Downloads 240

Authors: Behnaz Pahlousay, Farshad Kazemnejad, Elisa Palezzato, Michele Torielli

Abstract:

In this paper, we study the notions of connected domination number and of outer-connected domination number for middle graphs. Indeed, we obtain tight bounds for these numbers in terms of the order of the middle graph M(G). We also compute the outer-connected domination number of some families of graphs such as star graphs, cycle graphs, wheel graphs, complete graphs, complete bipartite graphs and some operation on graphs, explicitly. Moreover, some Nordhaus-Gaddum-like relations are presented for the outer-connected domination number of middle graphs.

Keywords: connected domination number, outer-connected dom- ination number, domination number, middle graph, nordhaus- gaddum-like relation.

Procedia PDF Downloads 37

Authors: Gete Umbrey, Saifur Rahman

Abstract:

Graphs are found to be most capable in computing, and its abstract structures have been applied in some specific computations and algorithms like in phase encoding controller, processor microcontroller, and synthesis of a CMOS switching network, etc. Being motivated by these works, we develop an independent approach to study semiring structures and various properties by defining the binary operations which in fact, seems analogous to an existing definition in some sense but with a different approach. This work emphasizes specifically on the construction of semigroup and semiring structures on the set of undirected graphs, and their properties are investigated therein. It is expected that the investigation done here may have some interesting applications in theoretical computer science, networking and decision making, and also on joining of two network systems.

Keywords: graphs, join and union of graphs, semiring, weighted graphs

Procedia PDF Downloads 148

Authors: Seyed Ahmad Mojallal

Abstract:

Let G be a connected threshold graph of order n with m edges and trace T. In this talk we give a lower bound on Laplacian energy in terms of n, m, and T of G. From this we determine the threshold graphs with the first four minimal Laplacian energies. We also list the first 20 minimal Laplacian energies among threshold graphs. Let σ=σ(G) be the number of Laplacian eigenvalues greater than or equal to average degree of graph G. Using this concept, we obtain the threshold graphs with the largest and the second largest Laplacian energies.

Keywords: Laplacian eigenvalues, Laplacian energy, threshold graphs, extremal graphs

Procedia PDF Downloads 388

Authors: Y. Wang

Abstract:

The Traveling salesman problem (TSP) is NP-hard in combinatorial optimization. The research shows the algorithms for TSP on the sparse graphs have the shorter computation time than those for TSP according to the complete graphs. We present an improved iterative algorithm to compute the sparse graphs for TSP by frequency graphs computed with frequency quadrilaterals. The iterative algorithm is enhanced by adjusting two parameters of the algorithm. The computation time of the algorithm is O(CN_maxn²) where C is the iterations, N_max is the maximum number of frequency quadrilaterals containing each edge and n is the scale of TSP. The experimental results showed the computed sparse graphs generally have less than 5n edges for most of these Euclidean instances. Moreover, the maximum degree and minimum degree of the vertices in the sparse graphs do not have much difference. Thus, the computation time of the methods to resolve the TSP on these sparse graphs will be greatly reduced.

Keywords: frequency quadrilateral, iterative algorithm, sparse graph, traveling salesman problem

Procedia PDF Downloads 233

Authors: T. Pathinathan, M. Peter

Abstract:

Fuzzy graphs incorporate concepts from graph theory with fuzzy principles. In this paper, we make a study on the properties of fuzzy graphs which are non-cyclic and are of two-dimensional in structure. In particular, this paper presents 2D structure or the structure of double layer for a non-cyclic fuzzy graph whose underlying crisp graph is non-cyclic. In any graph structure, introducing 2D structure may lead to an inherent cycle. We propose relevant conditions for 2D structured non-cyclic fuzzy graphs. These conditions are extended even to fuzzy graphs of the 3D structure. General theoretical properties that are studied for any fuzzy graph are verified to 2D structured or double layered fuzzy graphs. Concepts like Order, Degree, Strong and Size for a fuzzy graph are studied for 2D structured or double layered non-cyclic fuzzy graphs. Using different types of fuzzy graphs, the proposed concepts relating to 2D structured fuzzy graphs are verified.

Keywords: double layered fuzzy graph, double layered non–cyclic fuzzy graph, order, degree and size

Procedia PDF Downloads 400

Authors: Swapnil Gupta, C. Pandu Rangan

Abstract:

A uniquely restricted matching is defined to be a matching M whose matched vertices induces a sub-graph which has only one perfect matching. In this paper, we make progress on the open question of the status of this problem on interval graphs (graphs obtained as the intersection graph of intervals on a line). We give an algorithm to compute maximum cardinality uniquely restricted matchings on certain sub-classes of interval graphs. We consider two sub-classes of interval graphs, the former contained in the latter, and give O(|E|^2) time algorithms for both of them. It is to be noted that both sub-classes are incomparable to proper interval graphs (graphs obtained as the intersection graph of intervals in which no interval completely contains another interval), on which the problem can be solved in polynomial time.

Keywords: uniquely restricted matching, interval graph, matching, induced matching, witness counting

Procedia PDF Downloads 389

Authors: Vadim E. Levit, Eugen Mandrescu

Abstract:

A graph is well-covered if all its maximal independent sets are of the same size. A well-covered graph is 1-well-covered if deletion of every vertex of the graph leaves it well-covered. It is known that a graph without isolated vertices is 1-well-covered if and only if every two disjoint independent sets are included in two disjoint maximum independent sets. Well-covered graphs are related to combinatorial commutative algebra (e.g., every Cohen-Macaulay graph is well-covered, while each Gorenstein graph without isolated vertices is 1-well-covered). Our intent is to construct several infinite families of 1-well-covered graphs using the following known graph operations: corona, join, and rooted product of graphs. Adopting some known techniques used to advantage for well-covered graphs, one can prove that: if the graph G has no isolated vertices, then the corona of G and H is 1-well-covered if and only if H is a complete graph of order two at least; the join of the graphs G and H is 1-well-covered if and only if G and H have the same independence number and both are 1-well-covered; if H satisfies the property that every three pairwise disjoint independent sets are included in three pairwise disjoint maximum independent sets, then the rooted product of G and H is 1-well-covered, for every graph G. These findings show not only how to generate some more families of 1-well-covered graphs, but also that, to this aim, sometimes, one may use graphs that are not necessarily 1-well-covered.

Keywords: maximum independent set, corona, concatenation, join, well-covered graph

Procedia PDF Downloads 208

Authors: Robert Gold

Abstract:

Control flow graphs are a well-known representation of the sequential control flow structure of programs with a multitude of applications. Not only single functions but also sets of functions or complete programs can be modelled by control flow graphs. In this case the size of the graphs can grow considerably and thus makes it difficult for software engineers to analyse the control flow. Graph reductions are helpful in this situation. In this paper we define reductions to subsets of nodes. Since executions of programs are represented by paths through the control flow graphs, paths should be preserved. Furthermore, the composition of reductions makes a stepwise analysis approach possible.

Keywords: control flow graph, graph reduction, software engineering, software applications

Procedia PDF Downloads 552

Authors: Khidir R. Sharaf, Didar A. Ali

Abstract:

The nullity η (G) of a graph is the occurrence of zero as an eigenvalue in its spectra. A zero-sum weighting of a graph G is real valued function, say f from vertices of G to the set of real numbers, provided that for each vertex of G the summation of the weights f (w) over all neighborhood w of v is zero for each v in G.A high zero-sum weighting of G is one that uses maximum number of non-zero independent variables. If G is graph with an end vertex, and if H is an induced sub-graph of G obtained by deleting this vertex together with the vertex adjacent to it, then, η(G)= η(H). In this paper, a high zero-sum weighting technique and the end vertex procedure are applied to evaluate the nullity of t-tupple and generalized t-tupple graphs are derived and determined for some special types of graphs. Also, we introduce and prove some important results about the t-tupple coalescence, Cartesian and Kronecker products of nut graphs.

Keywords: graph theory, graph spectra, nullity of graphs, statistic

Procedia PDF Downloads 239

Authors: Jihad H. Asad

Abstract:

An expression for the Green’s function (GF) of anisotropic face cantered cubic (IFCC) lattice is evaluated analytically and numerically for a single impurity problem. The density of states (DOS), phase shift and scattering cross section are expressed in terms of complete elliptic integrals of the first kind.

Keywords: lattice Green's function, elliptic integral, physics, cubic lattice

Procedia PDF Downloads 466

Authors: B. Bouadjemi, S. Bentata, W. Benstaali, A. Abbad, T. Lantri, A. Zitouni

Abstract:

The purpose of this study was to investigate the structural,electronic and magnetic properties of the cubic praseodymium oxides perovskites PrMnO3. It includes our calculations based on the use of the density functional theory (DFT) with both generalized gradient approximation (GGA) and GGA+U approaches, The spin polarized electronic band structures and densities of states as well as the integer value of the magnetic moment of the unit cell (6 μB) illustrate that PrMnO3 is half-metallic ferromagnetic. The study prove that the compound is half-metallic ferromagnetic however the results obtained, make the cubic PrMnO3 a promising candidate for application in spintronics.

Keywords: cubic, DFT, electronic properties, magnetic moment, spintronics

Procedia PDF Downloads 465

Authors: S. R. Nayaka, Putta Swamy

Abstract:

Graph polynomial is one of the algebraic representations of the Graph. The degree polynomial is one of the simple algebraic representations of graphs. The degree polynomial of a graph G of order n is the polynomial Deg(G, x) with the coefficients deg(G,i) where deg(G,i) denotes the number of vertices of degree i in G. In this article, we investigate the behavior of the roots of some families of Graphs in the complex field. We investigate for the graphs having only integral roots. Further, we characterize the graphs having single roots or having real roots and behavior of the polynomial at the particular value is also obtained.

Keywords: degree polynomial, regular graph, minimum and maximum degree, graph operations

Procedia PDF Downloads 249

Authors: Josef Slapal

Abstract:

Digital images are approximations of real ones and, therefore, to be able to study them, we need the digital plane Z2 to be equipped with a convenient structure that behaves analogously to the Euclidean topology on the real plane. In particular, it is required that such a structure allows for a digital analogue of the Jordan curve theorem. We introduce certain adjacency graphs on the digital plane and prove digital Jordan curves for them thus showing that the graphs provide convenient structures on Z2 for the study and processing of digital images. Further convenient structures including the wellknown Khalimsky and Marcus-Wyse adjacency graphs may be obtained as quotients of the graphs introduced. Since digital Jordan curves represent borders of objects in digital images, the adjacency graphs discussed may be used as background structures on the digital plane for solving the problems of digital image processing that are closely related to borders like border detection, contour filling, pattern recognition, thinning, etc.

Keywords: digital plane, adjacency graph, Jordan curve, quotient adjacency

Procedia PDF Downloads 379

Authors: Shin-Shin Kao, Yuan-Kang Shih, Hsun Su

Abstract:

In this paper, we show that the conjecture of Chv tal, which states that any 1-tough graph is either a Hamiltonian graph or its complement contains a specific graph denoted by F, does not hold in general. More precisely, it is true only for graphs with six or seven vertices, and is false for graphs with eight or more vertices. A theorem is derived as a correction for the conjecture.

Keywords: complement, degree sum, hamiltonian, tough

Procedia PDF Downloads 289

Authors: B. Bouadjemi, S. Bentata, W. Benstaali, A. Abbad

Abstract:

The electronic and magnetic properties of the cubic praseodymium oxides perovskites PrMnO3 were calculated using the density functional theory (DFT) with both generalized gradient approximation (GGA) and GGA+U approaches, where U is on-site Coulomb interaction correction. The results show a half-metallic ferromagnetic ground state for PrMnO3 in GGA+U approached, while semi-metallic ferromagnetic character is observed in GGA. The results obtained, make the cubic PrMnO3 a promising candidate for application in spintronics.

Keywords: first-principles, electronic properties, transition metal, materials science

Procedia PDF Downloads 466

Authors: M. Khundadze, V. Varazashvili, N. Lejava, R. Jorbenadze

Abstract:

Phase transitions of cerium and neodymium are investigated by using high-temperature scanning calorimeter (HT-1500 Seteram). For cerium two types of transformation are detected: at 350-372 K - hexagonal close packing (hcp) - face-centered cubic lattice (fcc) transition, and at 880-960K the face-centered cubic lattice (fcc) transformation into body-centered cubic lattice (bcc). For neodymium changing of hexagonal close packing (hcp) into the body-centered cubic lattice (bcc) is detected at 1093-1113K. The thermal characteristics of transitions – enthalpy, entropy, temperature domains – are reported.

Keywords: cerium, calorimetry, enthalpy of phase transitions, neodymium

Procedia PDF Downloads 324

Authors: Walaa Obaidallah Alqarafi, Wafaa Mohammed Fakieh, Alaa Abdallah Altassan

Abstract:

Algebraic graph theory is defined as a bridge between algebraic structures and graphs. It has several uses in many fields, including chemistry, physics, and computer science. The prime graph is a type of graph associated with a ring R, where the vertex set is the whole ring R, and two vertices x and y are adjacent if either xRy=0 or yRx=0. However, the investigation of the prime graph over rings remains relatively limited. The behavior of this graph in extended rings, like R[x] and R[[x]], where R is a non-commutative ring, deserves more attention because of the wider applicability in algebra and other mathematical fields. To study the prime graphs over polynomials and power series rings, we used a combination of ring-theoretic and graph-theoretic techniques. This paper focuses on two invariants: the diameter and the girth of these graphs. Furthermore, the work discusses how the graph structures change when passing from R to R[x] and R[[x]]. In our study, we found that the set of strong zero-divisors of ring R represents the set of vertices in prime graphs. Based on this discovery, we redefined the vertices of prime graphs using the definition of strong zero divisors. Additionally, our results show that although the prime graphs of R[x] and R[[x]] are comparable to the graph of R, they have different combinatorial characteristics since these extensions contain new strong zero-divisors. In particular, we find conditions in which the diameter and girth of the graphs, as they expand from R to R[x] and R[[x]], do not change or do change. In conclusion, this study shows how extending a non-commutative ring R to R[x] and R[[x]] affects the structure of their prime graphs, particularly in terms of diameter and girth. These findings enhance the understanding of the relationship between ring extensions and graph properties.

Keywords: prime graph, diameter, girth, polynomial ring, power series ring

Procedia PDF Downloads 18

Authors: Saieed Akbari, Yousef Bagheri, Amir Hossein Ghodrati, Sima Saadat Akhtar

Abstract:

Let G be a simple graph with the vertex set V (G) and with the adjacency matrix A (G). The energy E (G) of G is defined to be the sum of the absolute values of all eigenvalues of A (G). Also let n and m be number of edges and vertices of the graph respectively. A regular graph is a graph where each vertex has the same number of neighbours. Given a graph G, its line graph L(G) is a graph such that each vertex of L(G) represents an edge of G; and two vertices of L(G) are adjacent if and only if their corresponding edges share a common endpoint in G. In this paper we show that for every regular graphs and also for every line graphs such that (G) 3 we have, E(G) 2nm + n 1. Also at the other part of the paper we prove that 2 (G) E(G) for an arbitrary graph G.

Keywords: eigenvalues, energy, line graphs, matching number

Procedia PDF Downloads 232

Authors: M. Khundadze, V. Varazashvili, N. Lejava, R. Jorbenadze

Abstract:

Phase transitions of cerium and neodymium are investigated by using high temperature scanning calorimeter (HT-1500 Seteram). For cerium two types of transformation are detected: at 350-372 K - hexagonal close packing (hcp) - face-centered cubic lattice (fcc) transition, and in 880-960K the face-centered cubic lattice (fcc) transformation into body-centered cubic lattice (bcc). For neodymium changing of hexagonal close packing (hcp) into body-centered cubic lattice (bcc) is detected at 1093-1113K. The thermal characteristics of transitions – enthalpy, entropy, temperature domains – are reported.

Keywords: cerium, calorimetry, neodymium, enthalpy of phase transitions, neodymium

Procedia PDF Downloads 369

Authors: Ranajay Bhowmick

Abstract:

Analysis of stresses for an infinitesimal tetrahedron leads to a situation where we obtain a cubic equation consisting of three stress invariants. This cubic equation, when solved for a definite condition, gives the principal stresses directly without requiring any cumbersome and time-consuming trial and error methods or iterative numerical procedures. Since the failure criterion of different materials are generally expressed as functions of principal stresses, an attempt has been made in this study to incorporate the solutions of the cubic equation in the form of principal stresses, obtained for a definite condition, into some of the established failure theories to determine their modified descriptions. It has been observed that the failure theories can be represented using the quadratic stress invariant and the orientation of the principal plane.

Keywords: cubic equation, stress invariant, trigonometric, explicit solution, principal stress, failure criterion

Procedia PDF Downloads 137

Authors: A. Chillali, M. Sahmoudi

Abstract:

In this paper we will give a method for encoding the elements of the ring of integers of sextic extension, namely L = Q(a,b) which is a rational quadratic over cubic field K =Q(a) where a^{2} is a rational square free integer and b is a root of irreducible polynomiale of degree 3.

Keywords: coding, integral bases, sextic, quadratic

Procedia PDF Downloads 297

Authors: Arnab Majumdar, Srimani Sen

Abstract:

In this paper, a vivid simulated study has been made on 35 GHz Ka-band window frequency in order to judge and compare the DC and high frequency properties of cubic ZnB-GaN with the existing hexagonal 4H-SiC. A flat profile p⁺pnn⁺ DDR structure of impatt is chosen and is optimized at a particular bias current density with respect to efficiency and output power taking into consideration the effect of mobile space charge also. The simulated results obtained reveals the strong potentiality of impatts based on both cubic ZnB-GaN and hexagonal 4H-SiC. The DC-to-millimeter wave conversion efficiency for cubic ZnB-GaN impatt obtained is 50% with an estimated output power of 2.83 W at an optimized bias current density of 2.5×10⁸ A/m². The conversion efficiency and estimated output power in case of hexagonal 4H-SiC impatt obtained is 22.34% and 40 W respectively at an optimum bias current density of 0.06×10⁸ A/m².

Keywords: cubic ZnB-GaN, hexagonal 4H-SiC, double drift impatt diode, millimetre wave, optimised bias current density, wide band gap semiconductor

Procedia PDF Downloads 359

Authors: Shazalina Mat Zin, Ahmad Abd. Majid, Ahmad Izani Md. Ismail, Muhammad Abbas

Abstract:

The generalized wave equation models various problems in sciences and engineering. In this paper, a new three-time level implicit approach based on cubic trigonometric B-spline for the approximate solution of wave equation is developed. The usual finite difference approach is used to discretize the time derivative while cubic trigonometric B-spline is applied as an interpolating function in the space dimension. Von Neumann stability analysis is used to analyze the proposed method. Two problems are discussed to exhibit the feasibility and capability of the method. The absolute errors and maximum error are computed to assess the performance of the proposed method. The results were found to be in good agreement with known solutions and with existing schemes in literature.

Keywords: collocation method, cubic trigonometric B-spline, finite difference, wave equation

Procedia PDF Downloads 541

Authors: Sarun Phibanchon, Yuttakarn Rattanachai

Abstract:

The quadratic-cubic nonlinear Schrodinger equation can be explained the weakly ion-acoustic waves in magnetized plasma with a slightly non-Maxwellian electron distribution by using the Madelung's fluid picture. However, the soliton solution to the quadratic-cubic nonlinear Schrodinger equation is determined by using the direct integration. By the characteristics of a soliton, the solution can be claimed that it's a soliton by considering its time evolution and their collisions between two solutions. These results are shown by applying the spectral method.

Keywords: soliton, ion-acoustic waves, plasma, spectral method

Procedia PDF Downloads 411

Authors: Mark L. Caay, Rodolfo E. Maza

Abstract:

In this paper, the authors define two new variants of domination in graphs: the marriage and the divorce domination. A subset S ⊆ V (G) is said to be a marriage dominating set of G if for every e ∈ E(G), there exists a u ∈ V (G) such that u is one of the end vertex of e. A marriage dominating set S ⊆ V (G) is said to be a divorce dominating set of G if G\S is a disconnected graph. In this study, the authors present conditions of graphs for which the marriage and the divorce domination will take place and for which the two sets will coincide. Furthermore, the author gives the necessary and sufficient conditions for marriage domination to avoid divorce.

Keywords: domination, decomposition, marriage domination, divorce domination, marriage theorem

Procedia PDF Downloads 17

Authors: Nileshkumar Vishnav, Aditya Tatu

Abstract:

A recent approach of representing graph signals and graph filters as polynomials is useful for graph signal processing. In this approach, the adjacency matrix plays pivotal role; instead of the more common approach involving graph-Laplacian. In this work, we follow the adjacency matrix based approach and corresponding algebraic signal model. We further expand the theory and introduce the concept of similarity of two graphs. The similarity of graphs is useful in that key properties (such as filter-response, algebra related to graph) get transferred from one graph to another. We demonstrate potential applications of the relation between two similar graphs, such as nonuniform filter design, DTMF detection and signal reconstruction.

Keywords: graph signal processing, algebraic signal processing, graph similarity, isospectral graphs, nonuniform signal processing

Procedia PDF Downloads 352

Authors: Abdul Jalil M. Khalaf, Esraa M. Kadhim

Abstract:

The Hosoya polynomial of a graph G is a graphical invariant polynomial that its first derivative at x= 1 is equal to the Wiener index and second derivative at x=1 is equal to the Hyper-Wiener index. In this paper we study the Hosoya polynomial of zero-divisor graphs.

Keywords: Hosoya polynomial, wiener index, Hyper-Wiener index, zero-divisor graphs

Procedia PDF Downloads 530

Authors: Bharti Gupta, V. K. Kukreja

Abstract:

A comprehensive numerical study is presented for the solution of time-dependent advection diffusion problems by using cubic B-spline collocation method. The linear combination of cubic B-spline basis, taken as approximating function, is evaluated using the zeros of shifted Chebyshev polynomials as collocation points in each element to obtain the best approximation. A comparison, on the basis of efficiency and accuracy, with the previous techniques is made which confirms the superiority of the proposed method. An asymptotic convergence analysis of technique is also discussed, and the method is found to be of order two. The theoretical analysis is supported with suitable examples to show second order convergence of technique. Different numerical examples are simulated using MATLAB in which the 3-D graphical presentation has taken at different time steps as well as different domain of interest.

Keywords: cubic B-spline basis, spectral norms, shifted Chebyshev polynomials, collocation points, error estimates

Procedia PDF Downloads 223

Authors: B. Bouadjemi, S. Bentata, W. Benstaali, A. Abbad, T. Lantri, A. Zitouni

Abstract:

The purpose of this study was to investigate the structural,electronic and magnetic properties of the cubic praseodymium oxides perovskites PrMnO3. It includes our calculations based on the use of the density functional theory (DFT) with both generalized gradient approximation (GGA) and GGA+U approaches, The spin polarized electronic band structures and densities of states aswellas the integer value of the magnetic moment of the unit cell (6 μB) illustrate that PrMnO3 is half-metallic ferromagnetic. The study shows that the robust half-metallicity makes the cubic PrMnO3 a promising candidate for application in spintronics.

Keywords: Perovskite, DFT, electronic properties, Magnetic moment, half-metallic

Procedia PDF Downloads 457