Search

A topological index is a number used in QSAR and QSPR research to assess the structural properties of a graph. The Sadhana and PI, polynomial-based topological indices, have been intensively explored in the study of chemical graph theory since a few years ago. These indices are computed using their related polynomials, however, in this study, we use an instantaneous and revolutionary approach to compute these indices for hexagonal boron nitride graphs and carbon nanotube structures. [ABSTRACT FROM AUTHOR]

A signed graph is a graph whose edges are labelled either positive or negative. Corresponding to the two signed distance matrices defined for signed graphs, we define two signed distance Laplacian matrices. We characterize singularity and calculate the rank of these matrices and find signed distance Laplacian spectra of some classes of unbalanced signed graphs. We derive most of these results by proving them more generally for weighted signed graphs. [ABSTRACT FROM AUTHOR]

Let G be a simple connected graph and A(G) be the adjacency matrix of G. Then G is said to have the anti-reciprocal eigenvalue property (property (−R)) if − 1 λ is an eigenvalue of A(G) whenever λ is an eigenvalue of A(G). Further, if λ and − 1 λ have the same multiplicity for each eigenvalue λ, then it is said to have the strong anti-reciprocal eigenvalue property (property (−SR)). A graph G is called unimodular if det (A (G)) = ± 1. We prove that if G satisfies property (−R), then G is unimodular. Further, we provide a complete characterization of all non-bipartite unicyclic graphs satisfying property (−SR) and prove that those graphs are necessarily coronas. In Ahmad et al. [Noncorona graphs with strong anti-reciprocal eigenvalue property. Linear Multilinear Alg. 2021;69(10):1878–1888], the authors constructed few classes of noncorona graphs using corona triangles, corona squares and corona pentagons which satisfy property (−SR). As a concluding remark, the authors suggested the following: 'property (−SR) seems to be hold for any class constructed in the same way using corona cycles of any finite length'. We prove it to be true and construct a more general class of noncorona graphs satisfying property (−SR). [ABSTRACT FROM AUTHOR]

In this article, we continue the classification work done in the first paper of the same name. With careful modifications of our previous approach, we are able to deduce (with two notable exceptions) which members of the previously introduced graph family manifest as the prime character degree graph of some solvable group. [ABSTRACT FROM AUTHOR]

G. Polya laid the foundation of counting polynomials in chemical graph theory. These polynomials can be associated with various graphs to signify their properties. In this study, a new concept has been introduced to construct the counting polynomials such as, Sadhana Theta and PI polynomials in terms of omega polynomial. A star expression has been established in order to transform equidistant into non equidistant edges. Furthermore, new relations have also been evolved to calculate Theta, PI and Sadhana Indices through Omega polynomial. [ABSTRACT FROM AUTHOR]

Let R be a finite commutative ring with non-zero identity. Let R × and J (R) be the group of unit elements and the Jacobson radical of R, respectively. The unit graph of the ring R, denoted by G (R) , is a graph whose vertex set is R and two distinct vertices x and y are adjacent if and only if x + y ∈ R × . If we relax this definition by dropping the term 'distinct', we obtain the closed unit graph, denoted by G ¯ (R). In this paper, we compute the adjacency spectrum of the graph G ¯ (R). We utilize this result to show that G (R) ≅ G (S) if and only if (R / J (R)) ≅ (S / J (S)) and | J (R) | = | J (S) | , where R and S are two arbitrary finite rings. Moreover, we determine when G (R) is a Ramanujan graph. We also deliver a necessary and sufficient condition for G (R) to be a strongly regular graph. Finally, we obtain the spectrum of a generalization of both unit and unitary Cayley graphs. [ABSTRACT FROM AUTHOR]

A T -gain graph is a triple Φ = (G , T , ϕ) consisting of an underlying graph G = (V (G) , E (G)) , the circle group T = { z ∈ C : | z | = 1 } and a gain function ϕ : E → → T , such that ϕ (e i j) = ϕ (e j i ) − 1 = ϕ (e j i) ¯ . In this paper, we focus our attention on the relations between the inertia indices of T -gain graph Φ and the inertia indices of its underlying graph G. We obtain sharp lower and upper bounds on p (Φ) (resp., n (Φ)) in terms of p (G) (resp., n (G)) and characterize those corresponding extremal T -gain graphs, respectively. As a corollary, we also characterize those signed graphs whose inertia indices obtaining the sharp bounds, respectively. [ABSTRACT FROM AUTHOR]

Given an n-vertex graph G with maximum degree Δ, the mixed graph D G is constructed from G by orienting some of its edges, where G is called the underlying graph of D G . Let r H (D G) be the H-rank of D G and let α (G) be the independence number of G. In this paper, we firstly determine the maximum nullity of n-vertex mixed graphs with maximum degree Δ. The corresponding extremal graphs are identified. We secondly establish upper and lower bounds on r H (D G) + α (G) , r H (D G) − α (G) , r H (D G) / α (G) , respectively. Finally, we characterize the relationship between the Hermitian energy and the H-rank of a mixed graph. [ABSTRACT FROM AUTHOR]

In this article, we investigate families of connected graphs which do not contain an odd cycle in their complement. Specifically, we consider graphs formed by two complete graphs connected in a particular way. We determine which of these graphs can or cannot occur as the prime character degree graph of a solvable group. An obvious expansion and generalization can also be considered, of which we make mention. [ABSTRACT FROM AUTHOR]

Given a graph G = (V, E), a function f: V → {0, 1, 2} is a total Roman {2}-dominating function if every vertex ʋ ∈ V for which f (ʋ) = 0 satisfies that ∑u∈N (ʋ)f (ʋ) ≥ 2, where N (ʋ) represents the open neighborhood of ʋ, and every vertex x ∈ V for which f (x) ≥ 1 is adjacent to at least one vertex y ∈ V such that f (y) ≥ 1. The weight of the function f is defined as ω(f) = ∑ʋ∈Vf (ʋ). The total Roman {2}-domination number, denoted by γt{R2}(G), is the minimum weight among all total Roman {2}-dominating functions on G. In this article we introduce the concepts above and begin the study of its combinatorial and computational properties. For instance, we give several closed relationships between this parameter and other domination related parameters in graphs. In addition, we prove that the complexity of computing the value γt{R2}(G) is NP-hard, even when restricted to bipartite or chordal graphs. [ABSTRACT FROM AUTHOR]

The energy E (G) of a graph G is the sum of the absolute values of all eigenvalues of G. More recently, the authors of Wong, Wang and Chu [Lower bounds of graph energy in terms of matching number. Linear Algebra Appl. 2018;549:276–286] obtained a lower bound for graph energy. They proved that, for a connected graph G apart from K 1 , K 3 and K p , q with 1 ≤ p q ≤ 4 , the energy of G is at least 2 5 . In the present paper, we aim to improve the lower bound from 2 5 to 6. The extreme graphs with energy 6 are characterized. [ABSTRACT FROM AUTHOR]

Given a graph G, the mixed graph D G is obtained from G by orienting some of its edges (G is also called the underlying graph of D G ). Let E H (D G) be the Hermitian energy of D G and let α ′ (G) be the matching number of the underlying graph G. In this paper, we first establish the inequality E H (D G) ⩾ 2 α ′ (G) and characterize all the mixed graphs D G which make E H (D G) = 2 α ′ (G) hold. Furthermore, we obtain 2 β (G) − 2 c (G) ⩽ E H (D G) ⩽ 2 β (G) Δ (G) , where β (G) , c (G) and Δ (G) are, respectively, the vertex cover number, the number of odd cycles and the maximum degree of graph G. The lower bound is attained if and only if D G is switching equivalent to its underlying graph G, where G is the disjoint union of some complete bipartite graphs each of which contains a perfect matching, together with some isolated vertices. The upper bound is best possible. By our results in this paper, some main results in Tian FL, Wong D. [Relation between the skew energy of an oriented graph and its matching number. Discrete Appl Math. 2017;222:179–184]; Wang L, Ma XB. [Bounds of graph energy in terms of vertex cover number. Linear Algebra Appl. 2017;517:207–216]; Wong D, Wang XL, Chu R. [Lower bounds of graph energy in terms of matching number. Linear Algebra Appl. 2018;549:276–286] can be deduced in a unified approach. [ABSTRACT FROM AUTHOR]

Formally, a signed graphS is a pair () that consists of a graph and a sign mapping called signature from E to the sign group {+, -}. Given a signed graph S and a positive integer t, the t-path signed graph of S is a signed graph whose vertex set is V(S) and two vertices are adjacent if and only if there exists a path of length t between these vertices and then by defining its sign to be '-' if and only if in every such path of length t in S all the edges are negative. The negation of a signed graph S is a signed graph obtained from S by reversing the sign of every edge of S. Two signed graphs and on the same underlying graph are switching equivalent if it is possible to assign signs ' ' ('plus') or ' ' ('minus') to the vertices of such that by reversing the sign of each of its edges that have received opposite signs at its ends, one obtains. In this paper, we characterize signed graphs whose negations are switching equivalent to their t-path signed graphs for and also characterize signed graphs such that the spectrum of their t-path signed graphs, where , and 2, is symmetric about the origin. [ABSTRACT FROM AUTHOR]

A cograph is a simple graph which contains no path on 4 vertices as an induced subgraph. We consider the eigenvalues of adjacency matrices of cographs and prove that a graph G is a cograph if and only if no induced subgraph of G has an eigenvalue in the interval. It is also shown that the multiplicity of any eigenvalue of a cograph G does not exceed the sum of multiplicities of 0 and as eigenvalues of G. We introduce a partial order on the vertex set of graphs G in terms of inclusions among the open and closed neighbourhoods of vertices, and conjecture that the multiplicity of any eigenvalue of a cograph G except for does not exceed the maximum size of an antichain with respect to that partial order. In two extreme cases (in particular for threshold graphs), the conjecture is shown to be true. Finally, we prove that bipartite -free graphs have no eigenvalue in the intervals and (0, 1 / 2). [ABSTRACT FROM AUTHOR]

LetRbe a commutative ring andZ(R)* be its set of all nonzero zero-divisors. Theannihilator graphof a commutative ringRis the simple undirected graphAG(R) with verticesZ(R)*, and two distinct verticesxandyare adjacent if and only ifann(xy)≠ann(x)∪ann(y). The notion of annihilator graph has been introduced and studied by Badawi [8]. In this paper, we classify the finite commutative rings whoseAG(R) are projective. Also we determine all isomorphism classes of finite commutative rings with identity whoseAG(R) has genus two. [ABSTRACT FROM PUBLISHER]

Letdenote the class ofc-cyclic graphs withnvertices, girthandpendant vertices. In this paper, we determine the unique extremal graph with largest signless Laplacian spectral radius and Laplacian spectral radius in the class of connectedc-cyclic graphs withvertices, girthgand at mostpendant vertices, respectively, and the unique extremal graph with largest signless Laplacian spectral radius ofwhenand, and we also identify the unique extremal graph with largest Laplacian spectral radius inin the caseand eitherandgis even orandgis odd. Our results extends the corresponding results of [Sci. Sin. Math. 2010;40:1017–1024, Electron. J. Combin. 2011; 18:p.183, Comput. Math. Appl. 2010;59:376–381, Electron. J. Linear Algebra. 2011;22:378–388 and J. Math. Res. Appl. 2014;34:379–391]. [ABSTRACT FROM AUTHOR]

LetR = k[x1,…,xn], wherekis a field. The path ideal (of lengtht) of a directed graphGis the monomial ideal, denoted byIt(G), whose generators correspond to the directed paths of lengthtinG. We determine all the graded Betti numbers of the path ideal of a directed rooted tree with respect to some graphical terms. [ABSTRACT FROM AUTHOR]

The total irregularity of a simple undirected graph G is denoted by irrt(G) and is defined as irrt(G) = 1/2 ... |d(u) - d(v)|. In this paper, we introduce the notion of edge-transformation in relation to total irregularity of simple graphs with at least one cut edge as well as an edge-joint between two graphs. We also introduce the notion of total irregularity with respect to in-degree and out-degree in directed graphs. We also introduce the concept of total irregularity in respect of in-degree and out-degree in simple directed graphs. These invariants are called total in-irregularity and total out-irregularity, respectively. In this paper, we initiate a study on these parameters of given simple undirected graphs and simple digraphs. [ABSTRACT FROM AUTHOR]

This paper introduces the notions of a zero-divisor labeling and the zero-divisor index of a graph using the zero-divisors of a commutative ring. Viewed in this way, the usual zero-divisor graph is a maximal graph with respect to a zero-divisor labeling. We also study optimal zero-divisor labelings of a finite graph. [ABSTRACT FROM PUBLISHER]

An oriented graphis a digraph without loops and multiple arcs, whereis called the underlying graph of. Letdenote the skew-adjacency matrix of. The rank ofis called the skew-rank of, denoted by, which is even sinceis skew symmetric. Recently, Qu and Yu proved thatfor an oriented bicyclic graphwith pendant vertices and with two edge-disjoint cycles of sizeand. In this paper, we extend this result to a more general case. It is proved thatifis a connected oriented graph withpairwise edge-disjoint cycles of size. Moreover, the extremal graphsattaining the lower bound are characterized. [ABSTRACT FROM PUBLISHER]

LetRbe a commutative ring with nonzero identity, and letIbe an ideal ofR. The ideal-based zero-divisor graph ofR, denoted by ΓI(R), is the graph whose vertices are the set {x∈R\I|xy∈Ifor somey∈R \ I} and two distinct verticesxandyare adjacent if and only ifxy∈I. Define the comaximal graph ofR, denoted byCG(R), to be a graph whose vertices are the elements ofR, where two distinct verticesaandbare adjacent if and only ifRa+Rb=R. A nonempty setS ⊆ Vof a graphG=(V, E) is a dominating set ofGif every vertex inVis either inSor is adjacent to a vertex inS. The domination numberγ(G) ofGis the minimum cardinality among the dominating sets ofG. The main object of this paper is to study the dominating sets and domination number of ΓI(R) and the comaximal graphCG2(R) \J(R) (orCGJ(R) for short) whereCG2(R) is the subgraph ofCG(R) induced on the nonunit elements ofRandJ(R) is the Jacobson radical ofR. [ABSTRACT FROM PUBLISHER]

The paper presents designs that allow detection of mixed effects when performing preliminary screening of the inputs of a scalar function ofdinput factors, in the spirit of Morris' Elementary Effects approach. We introduce the class of-cycle equitable designs as those that enable computation of exactlycsecond-order effects on all possible pairs of input factors. Using these designs, we propose a fast Mixed Effects screening method, that enables efficient identification of the interaction graph of the input variables. Design definition is formally supported on the establishment of an isometry between sub-graphs of the unit cubeequipped of the Manhattan metric, and a set of polynomials inon which a convenient inner product is defined. In the paper we present systems of equations that recursively define these-cycle equitable designs for generic values of, from which direct algorithmic implementations are derived. Application cases are presented, illustrating the application of the proposed designs to the estimation of the interaction graph of specific functions. [ABSTRACT FROM PUBLISHER]

LetRbe a commutative ring with identity. The set 𝕀(R) of all ideals ofRis a bounded semiring with respect to ordinary addition, multiplication and inclusion of ideals. The zero-divisor graph of 𝕀(R) is called the annihilating-ideal graph ofR, denoted by 𝔸𝔾(R). We write 𝒢 for the set of graphs whose cores consist of only triangles. In this paper, the types of the graphs in 𝒢 that can be realized as either the zero-divisor graphs of bounded semirings or the annihilating-ideal graphs of commutative rings are determined. A necessary and sufficient condition for a ringRsuch that 𝔸𝔾(R) ∈ 𝒢 is given. Finally, a complete characterization in terms of quotients of polynomial rings is established for finite ringsRwith 𝔸𝔾(R) ∈ 𝒢. Also, a connection between finite rings and their corresponding graphs is realized. [ABSTRACT FROM AUTHOR]

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness ofP4-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for anyP4-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced. [ABSTRACT FROM PUBLISHER]

LetGbe a simple non-complete graph of ordern. Ther-component edge connectivity ofGdenoted as λr(G) is the minimum number of edges that must be removed fromGin order to obtain a graph with (at least)rconnected components. The concept ofr-component edge connectivity generalizes that of edge connectivity by taking into account the number of components of the resulting graph. In this paper we establish bounds of thercomponent edge connectivity of an important family of interconnection network models, the generalized Petersen graphs GP(n, k) in whichnandkare relatively prime integers. [ABSTRACT FROM AUTHOR]

In this paper we obtain information about the hyperbolicity constant of cubic graphs. They are a very interesting class of graphs with many applications; furthermore, they are also very important in the study of Gromov hyperbolicity, since for any graphGwith bounded maximum degree there exists a cubic graphG* such thatGis hyperbolic if and only ifG* is hyperbolic. We find some characterizations for the cubic graphs which have small hyperbolicity constants, i.e. the graphs which are like trees (in the Gromov sense). Besides, we obtain bounds for the hyperbolicity constant of the complement graph of a cubic graph; our main result of this kind says that for any finite cubic graphGwhich is not isomorphic either toK4or toK3, 3, the inequalities 5k/4≤δ (Ḡ)≤3k/2 hold, ifkis the length of every edge inG. [ABSTRACT FROM AUTHOR]

LetMbe a module over a commutative ring, and letSpec(M) be the collection of all prime submodules ofM. We topologizeSpec(M) with Zariski topology, which is analogous to that forSpec(R), and for a nonempty subsetTofSpec(M), we introduce a new graphG(τT), called the Zariski topology-graph. This graph helps us to study the algebraic (resp. topological) properties ofM(resp.Spec(M)) by using the graph theoretical tools. [ABSTRACT FROM AUTHOR]

The notion of equitable colouring was introduced by Meyer in 1973. In this paper we find the equitable chromatic number χ=for the line graph of Knödel graphsL(WΔ, n), central graph of Knödel graphsC(WΔ, n) and corona graph of Knödel graphsWΔ, m°WΔ, n. As a by-product we obtain a new class of graphs that confirm Equitable Colouring Conjecture. [ABSTRACT FROM PUBLISHER]

It is well known that all starlike trees, i.e. trees with exactly one vertex of degree at least three, are determined by their Laplacian spectrum. A double starlike tree is a tree with exactly two vertices of degree at least three. In 2009, the following question was posed: Are all the double starlike trees determined by their Laplacian spectra? In this direction, it was proved that one special double starlike treeis determined by its Laplacian spectrum, whereis a tree obtained by joiningpendant vertices to an end vertex of a path of orderand then joiningpendant vertices to another end of the path. Also, the banana treeis a tree obtained by joining a vertex to one arbitrary pendant vertex of each copy of-copies of. Recently, it is shown thatis determined by its Laplacian spectrum as well. In this paper, we study the Laplacian spectral characterization ofand. We show thatandare determined by their Laplacian spectra, for. [ABSTRACT FROM PUBLISHER]

In this article, graph blow-up is used to study the implements of the co-maximal graphand the co-maximal ideal graph 𝒞(R) of a commutative ringR. We show that for a ringRwith finitely many maximal ideals, the graph 𝒞(R) is a blow-up of a Boolean graph, and we give more detailed structure of the graphsand 𝒞(R) as blow-ups of Boolean graphs. We determine for what ringsR, 𝒞(R) oris a finite graph, respectively. In the end, we get some new results for rings by taking advantage of the graph. [ABSTRACT FROM PUBLISHER]

For a commutative ringRwith identity, the annihilating-ideal graph ofR, denoted 𝔸𝔾(R), is the graph whose vertices are the nonzero annihilating ideals ofRwith two distinct vertices joined by an edge when the product of the vertices is the zero ideal. We will generalize this notion for an idealIofRby replacing nonzero ideals whose product is zero with ideals that are not contained inIand their product lies inIand call it theannihilating-ideal graphofRwith respect toI, denoted 𝔸𝔾I(R). We discuss when 𝔸𝔾I(R) is bipartite. We also give some results on the subgraphs and the parameters of 𝔸𝔾I(R). [ABSTRACT FROM AUTHOR]

LetGbe the circulant graphCn(S) with, and letI(G) denote the edge ideal in the ringR = k[x1,…,xn]. We consider the problem of determining whenGis Cohen–Macaulay, i.e,R/I(G) is a Cohen–Macaulay ring. Because a Cohen–Macaulay graphGmust be well-covered, we focus on known families of well-covered circulant graphs of the formCn(1, 2,…,d). We also characterize which cubic circulant graphs are Cohen–Macaulay. We end with the observation that even though the well-covered property is preserved under lexicographical products of graphs, this is not true of the Cohen–Macaulay property. [ABSTRACT FROM AUTHOR]

Given a networkG, it is known that the Bonacich centrality of the bipartite graphB(G) associated withGcan be obtained in terms of the centralities of the line graphL(G) associated withGand the centrality of the networkG+gr(whose adjacency matrix is obtained by adding to the adjacency matrixA(G) the diagonal matrixD=bij, wherebiiis the degree of nodeiinG) and conversely. In this contribution, we use the centrality ofGto estimate the centrality ofG+grand show that the error committed is bounded by some measure of the irregularity ofG. This estimate gives an analytical comparison of the eigenvector centrality ofGwith the centrality ofL(G) in terms of some irregularity measure ofG. [ABSTRACT FROM PUBLISHER]

LetRbe a commutative ring andZ(R) be its set of all zero-divisors. Thetotal graphofR, denoted byTΓ(R), is the undirected graph with vertex setRand two distinct verticesxandyare adjacent if and only ifx + y ∈ Z(R).denotes the complement ofTΓ(R). The study on total graphs has been initiated by D. F. Anderson and A. Badawi [2]. In this article, we characterize all commutative rings whose total graph (or its complement) is in some known class of graphs. Also we determine the structurewhenever |Reg(R)| = 2. Further, we obtain certain necessary conditions forto be connected wheneveris connected and prove that. It is also proved that ifdiam(TΓ(R)) = 2, thenTΓ(R) is Hamiltonian, which is a generalization of a characterization proved by S. Akbari et al. [1]. [ABSTRACT FROM PUBLISHER]

In this paper, we consider the problem of determining the minimal cardinality of double resolving sets for prism graphs. It is proved that the minimal cardinality is equal to four ifis even and equal to three ifis odd. [ABSTRACT FROM PUBLISHER]

LetRbe a commutative ring with identity 1 ≠ 0. A nonzero elementainRis said to be a Smarandache zero-divisor if there exist three different nonzero elementsx,y, andb(≠ a) inRsuch thatax = ab = by = 0, butxy ≠ 0. We will generalize this notion to the Smarandache vertex of an arbitrary simple graph and characterize the Smarandache zero-divisors of commutative rings (resp. with respect to an ideal) via their associated zero-divisor graphs. We illustrate them with examples and prove some interesting results about them. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring and Z(R) be its set of all zero-divisors. The total graph of R, denoted by TΓ(R), is the undirected graph with vertex set R, and two distinct vertices x and y are adjacent if and only ifx + y ∈ Z(R). Maimani et al. [13] determined all isomorphism classes of finite commutative rings whose total graph has genus at most one. In this article, after enumerating certain lower and upper bounds for genus of the total graph of a commutative ring, we characterize all isomorphism classes of finite commutative rings whose total graph has genus two. [ABSTRACT FROM PUBLISHER]

Let R be a commutative ring with non zero unity. Let Ω(R) be a graph with vertices as elements of R whose two distinct vertices x and y are adjacent if and only if Rx + Ry = R. A graph (V, E) is said to be a split graph if V is the disjoint union of two sets K and S where K induces a complete subgraph and S is an independent set. We investigate the properties of R when Ω(R) is split. [ABSTRACT FROM PUBLISHER]

A function f: V→−1,+1, defined on the vertices of a graph G, is a signed maximum-clique transversal function if ∑ u∈V(Q) f(u)≥1 for each maximum clique Q of G. The weight of a signed maximum-clique transversal function is w(f)=∑ v∈V(G) f(v). The signed maximum-clique transversal number of G, denoted by , is the minimum weight of a signed maximum-clique transversal function of G. In this paper, we establish a tight lower bound on for an arbitrary graph G and an upper bound on for a k-regular graph G with ω(G)=k, and we characterize the extremal graphs achieving the upper bound. Meanwhile, we establish a lower bound on for a connected claw-free cubic graph, and characterize the extremal graphs achieving the lower bound. For a connected claw-free 4-regular graph G with ω(G)=3, we present sharp bounds on and characterize the extremal graphs achieving the lower bound. [ABSTRACT FROM AUTHOR]

The new concept of multilevel network is introduced in order to embody some topological properties of complex systems with structures in the mesoscale, which are not completely captured by the classical models. This new model, which generalizes the hyper-network and hyper-structure models, fits perfectly with several real-life complex systems, including social and public transportation networks. We present an analysis of the structural properties of the multilevel network, including the clustering and the metric structures. Some analytical relationships amongst the efficiency and clustering coefficient of this new model and the corresponding parameters of the underlying network are obtained. Finally, some random models for multilevel networks are given to illustrate how different multilevel structures can produce similar underlying networks and therefore that the mesoscale structure should be taken into account in many applications. [ABSTRACT FROM PUBLISHER]

The r-component connectivity κ r (G) of the non-complete graph G is the minimum number of vertices whose deletion results in a graph with at least r components. So, κ2 is the usual connectivity. In this paper, we determine the r-component connectivity of the hypercube Q n for r=2, 3, …, n+1, and we classify all the corresponding optimal solutions. [ABSTRACT FROM PUBLISHER]

The star graph interconnection network has been recognized as an attractive alternative to the hypercube for its nice topological properties. Unlike previous research concerning the issue of embedding exactly one Hamiltonian cycle into an injured star network, this paper addresses the maximum number of fault-free mutually independent Hamiltonian cycles in the faulty star network. To be precise, let SG n denote an n-dimensional star network in which f≤n-3 edges may fail accidentally. We show that there exist (n-2-f)-mutually independent Hamiltonian cycles rooted at any vertex in SG n if n∈{3, 4}, and there exist (n-1-f)-mutually independent Hamiltonian cycles rooted at any vertex in SG n if n≥5. [ABSTRACT FROM AUTHOR]

A Hamiltonian cycle C=〈 u1, u2, ..., un(G), u1 〉 with n(G)=number of vertices of G, is a cycle C(u1; G), where u1 is the beginning and ending vertex and ui is the ith vertex in C and ui≠uj for any i≠j, 1≤i, j≤n(G). A set of Hamiltonian cycles {C1, C2, ..., Ck} of G is mutually independent if any two different Hamiltonian cycles are independent. For a hamiltonian graph G, the mutually independent Hamiltonianicity number of G, denoted by h(G), is the maximum integer k such that for any vertex u of G there exist k-mutually independent Hamiltonian cycles of G starting at u. In this paper, we prove that h(Bn)=n-1 if n≥4, where Bn is the n-dimensional bubble-sort graph. [ABSTRACT FROM AUTHOR]

The simplest graph drawing method is that of putting the vertices of a graph on a line (spine) and drawing the edges as half-circles on k half planes (pages). Such drawings are called k-page book drawings and the minimal number of edge crossings in such a drawing is called the k-page crossing number. In a one-page book drawing, all edges are placed on one side of the spine, and in a two-page book drawing all edges are placed either above or below the spine. The one- and two-page crossing numbers of a graph provide upper bounds for the standard planar crossing. In this paper, we derive the exact one-page crossing numbers for four-row meshes, present a new proof for the one-page crossing numbers of Halin graphs, and derive the exact two-page crossing numbers for circulant graphs [image omitted] . We also give explicit constructions of the optimal drawings for each kind of graph. [ABSTRACT FROM AUTHOR]

It is important to know how to improve a network when dealing with performance and security. We characterize the optimal design of a network for efficiency or vulnerability giving the extreme networks for those parameters. Moreover, we give an algorithm to improve the vulnerability of a given network when adding a new link. For efficiency, we present two facts that have to be considered in order to improve it when adding a new link, and we calculate bounds for the increment. [ABSTRACT FROM AUTHOR]

Some research on the folded Petersen cube networks have been published for the past several years due to its favourite properties. In this paper, we consider the fault-tolerant hamiltonicity and the fault-tolerant hamiltonian connectivity of the folded Petersen cube networks. We use FPQn, k to denote the folded Petersen cube networks of parameters n and k. In this paper, we show that FPQn, k-F remains hamiltonian for any F ⊆ V(FPQn, k)∪E(FPQn, k) with |F|≤n+3k-2 and FPQn, k-F remains hamiltonian connected for any F ⊆ V(FPQn, k)∪E(FPQn, k) with |F|≤n+3k-3 if (n, k)∉{(0, 1)}∪{(n, 0) | n is a positive integer}. Moreover, this result is optimal. [ABSTRACT FROM AUTHOR]

This article studies the zero divisor graph for the ring of Gaussian integers modulo n, Γ (n[i]). For each positive integer n, the number of vertices, the diameter, the girth and the case when the dominating number is 1 or 2 is found. Complete characterizations, in terms of n, are given of the cases in which Γ (n[i]) is complete, complete bipartite, planar, regular or Eulerian. [ABSTRACT FROM AUTHOR]

In the present article, for bipartite graphs and chordal graphs, their exterior algebraic shifted graph and their symmetric algebraic shifted graph are studied. First, we will determine the symmetric algebraic shifted graph of complete bipartite graphs. It turns out that for a ≥ 3 and b ≥ 3, the exterior algebraic shifted graph of the complete bipartite graph Ka,b of size a, b is different from the symmetric algebraic shifted graph of Ka,b. Second, we will show that the exterior algebraic shifted graph of any chordal graph G coincides with the symmetric algebraic shifted graph of G. In addition, it will be shown that the exterior algebraic shifted graph of any chordal graph G is equal to some combinatorial shifted graph of G. [ABSTRACT FROM AUTHOR]

Let R be a commutative ring with nonzero identity and let I be an ideal of R . The zero-divisor graph of R with respect to I , denoted by G I ( R ), is the graph whose vertices are the set { x ? R \ I | xy ? I for some y ? R \ I } with distinct vertices x and y adjacent if and only if xy ? I . In the case I = 0, G 0 ( R ), denoted by G( R ), is the zero-divisor graph which has well known results in the literature. In this article we explore the relationship between G I ( R ) ? G J ( S ) and G( R / I ) ? G( S / J ). We also discuss when G I ( R ) is bipartite. Finally we give some results on the subgraphs and the parameters of G I ( R ). [ABSTRACT FROM AUTHOR]

The geometry of the moduli space of stable spin curves is studied, with emphasis on its combinatorial properties. In this context, the standard graph-theoretic framework is not just a book-keeping device: some purely combinatorial results are proved, having moduli-theoretic applications. In particular, certain strata of the moduli space of stable curves are characterized by a (finite) set of integers, measuring the non-reducedness of the scheme of spin curves, and definable in purely graph-theoretical terms. [ABSTRACT FROM AUTHOR]