Search

A multigraph is a graph with possible multiple edges, but no loops. Let t be a positive integer. Let G t be the set of simple graphs (or multigraphs) such that for each G ∈ G t there exist at least t + 1 non-empty disjoint proper subsets V 1 , V 2 , ... , V t + 1 ⊆ V (G) satisfying V (G) ∖ (V 1 ∪ V 2 ∪ ⋯ ∪ V t + 1) ≠ ϕ and edge connectivity κ ′ (G) = e (V i , V (G) ∖ V i) for i = 1 , 2 , ... , t + 1. Let D (G) and A (G) denote the degree diagonal matrix and adjacency matrix of a simple graph (or a multigraph) G , and let μ i (G) be the i th largest eigenvalue of the Laplacian matrix L (G) = D (G) + A (G). In this paper, we investigate the relationship between μ n − 2 (G) and edge connectivity or spanning tree packing number of a graph G ∈ G 1 , respectively. We also give the relationship between μ n − 3 (G) and edge connectivity or spanning tree packing number of a graph G ∈ G 2 , respectively. Moreover, we generalize all the results about L (G) to a more general matrix a D (G) + A (G) , where a is a real number with a ≥ − 1. [ABSTRACT FROM AUTHOR]

Edge connectivity is often used to capture edge fault tolerance. As for most common networks, their edge connectivity is exactly equal to their minimum degree. Edge matroidal connectivity and conditional edge matroidal connectivity are two new graph edge connectivity parameters that can be defined when a partition of the edge set is given, for example when the network is built with different kinds of edges having different expected faultiness. And those two edge connectivity parameters can measure edge fault tolerance more than the traditional definition. The edge matroidal connectivity is based on the associated edge partition and the other is a generalization called conditional edge matroidal connectivity. We analyze these new parameters on hypercubes and folded hypercubes which are well studied networks. In this study, we consider their standard dimensional partition of the edges. This study leads to more structural insights about edge connectivity and yields many interesting questions. • We propose two new edge connectivity parameters for a graph based on the associated edge partition. • The two edge connectivity parameters are edge matroidal connectivity and conditional edge matroidal connectivity. • We analyze the (conditional) edge matroidal connectivity for hypercubes and folded hypercubes. [ABSTRACT FROM AUTHOR]

Let G be a simple undirected connected graph. The signless Laplacian Estrada, Laplacian Estrada and Estrada indices of a graph G is the sum of the exponentials of the signless Laplacian eigenvalues, Laplacian eigenvalues and eigenvalues of G , respectively. The present work derives an upper bound for the Estrada index of a graph as a function of its chromatic number, in the family of graphs whose color classes have order not less than a fixed positive integer. The graphs for which the upper bound is tight is obtained. Additionally, an upper bound for the Estrada Index of the complement of a graph in the previous family of graphs with two color classes is given. A Nordhaus-Gaddum type inequality for the Laplacian Estrada index when G is a bipartite graph with color classes of order not less than 2, is presented. Moreover, a sharp upper bound for the Estrada index of the line graph and for the signless Laplacian index of a graph in terms of connectivity is obtained. [ABSTRACT FROM AUTHOR]

Let H be a connected hypergraph with minimum degree δ (H) , edge connectivity λ (H) and vertex connectivity κ (H). An r -uniform hypergraph is p - partite if its vertex set can be partitioned into p parts, and every edge contains at most one vertex from each part, where p ≥ r ≥ 2. Volkmann (1989) and Topp and Volkmann (1993) established sufficient conditions on p -partite graphs G implying λ (G) = δ (G) or κ (G) = λ (G). In this paper we generalize these well-known results to p -partite uniform hypergraphs. [ABSTRACT FROM AUTHOR]

Jaeger in 1979 showed that every 4-edge-connected graph is supereulerian, graphs that have spanning eulerian subgraphs. Catlin in 1988 sharpened Jaeger's result by showing that every 4-edge-connected graph is collapsible, graphs that are contractible configurations of supereulerian graphs. To further study collapsible subgraphs of a 4-edge-connected graph, in Catlin et al. (2009), it is shown that every 4-edge-connected graph remains collapsible after removing any two edges. We prove the following. • [(i)] Every 4-edge-connected G contains two vertices x , y such that one of x and y has minimum degree in G and both G − x and G − y are collapsible. • [(ii)] Let G be a 4-edge-connected graph and let X ⊂ E (G) be an edge subset with | X | ≤ 3. Then G − X is collapsible if and only if X is not contained in a 4-edge-cut of G. • [(iii)] Let G be a 4-edge-connected graph and let X ⊂ E (G) be an edge subset with | X | ≤ 4. Then G − X is collapsible if and only if G − X is not contractible to a member in { K 2 c , K 2 , K 2 , 2 , K 2 , 3 , K 2 , 4 }. These extend former results of Jaeger (1979) and Catlin (1988). [ABSTRACT FROM AUTHOR]

Abstract Let G be a graph and L (G) be its line graph. In 1969, Chartrand and Stewart proved that κ ′ (L (G)) ≥ 2 κ ′ (G) − 2 , where κ ′ (G) and κ ′ (L (G)) denote the edge connectivity of G and L (G) respectively. We show a similar relationship holds for the essential edge connectivity of G and L (G) , written κ e ′ (G) and κ e ′ (L (G)) , respectively. In this note, it is proved that if L (G) is not a complete graph and G does not have a vertex of degree two, then κ e ′ (L (G)) ≥ 2 κ e ′ (G) − 2. An immediate corollary is that κ (L 2 (G)) ≥ 2 κ (L (G)) − 2 for such graphs G , where the vertex connectivity of the line graph L (G) and the second iterated line graph L 2 (G) are written as κ (L (G)) and κ (L 2 (G)) respectively. [ABSTRACT FROM AUTHOR]

The generalized A B C index of a graph G , denoted by A B C α ( G ) , is defined as the sum of weights ( d i + d j − 2 d i d j ) α over all edges v i v j of G , where α is an arbitrary non-zero real number, and d i is the degree of vertex v i of G . In this paper, we first prove that the generalized A B C index of a connected graph will increase with addition of edge(s) if α < 0 or 0 < α ≤ 1 ∕ 2 , which provides a useful tool for the study of extremal properties of the generalized A B C index. By means of this result, we then characterize the graphs having the maximal A B C α value for α < 0 among all connected graphs with given order and vertex connectivity, edge connectivity, or matching number. Our work extends some previously known results. [ABSTRACT FROM AUTHOR]

For an undirected simple graph G , the line graph L ( G ) is the graph whose vertex set is in one-to-one correspondence with the edge set of G where two vertices are adjacent if their corresponding edges in G have a common vertex. The energy E ( G ) is the sum of the absolute values of the eigenvalues of G . The vertex connectivity κ ( G ) is referred as the minimum number of vertices whose deletion disconnects G . The positive inertia ν + ( G ) corresponds to the number of positive eigenvalues of G . Finally, the matching number β ( G ) is the maximum number of independent edges of G . In this paper, we derive a sharp upper bound for the energy of the line graph of a graph G on n vertices having a vertex connectivity less than or equal to k . In addition, we obtain upper bounds on E ( G ) in terms of the edge connectivity, the inertia and the matching number of G . Moreover, a new family of hyperenergetic graphs is obtained. [ABSTRACT FROM AUTHOR]

Denote the sum of squares of all distances between all pairs of vertices in G by S ( G ) . In this paper, sharp bounds on the S ( G ) are determined for several classes of connected bipartite graphs. All the extremal graphs having the minimal S ( G ) in the class of all connected n -vertex bipartite graphs with a given vertex connectivity (resp. edge-connectivity) can be identified. [ABSTRACT FROM AUTHOR]

A multigraph is a graph with possible multiple edges, but no loops. The multiplicity of a multigraph is the maximum number of edges between any pair of vertices. We prove that, for a multigraph G with multiplicity m and minimum degree δ ≥ 2 k , if the algebraic connectivity is greater than min ⁡ { 2 k − 1 ⌈ ( δ + 1 ) / m ⌉ , 2 k − 1 2 } , then G has at least k edge-disjoint spanning trees; for a multigraph G with multiplicity m and minimum degree δ ≥ k , if the algebraic connectivity is greater than min ⁡ { 2 ( k − 1 ) ⌈ ( δ + 1 ) / m ⌉ , k − 1 } , then the edge connectivity is at least k . These extend some earlier results. A balloon of a graph G is a maximal 2-edge-connected subgraph that is joined to the rest of G by exactly one cut-edge. We provide spectral conditions for the number of balloons in a multigraph, which also generalizes an earlier result. [ABSTRACT FROM AUTHOR]

For G being a graph with n vertices and m edges, and with Laplacian eigenvalues μ 1 ≥ μ 2 ≥ ⋯ ≥ μ n − 1 ≥ μ n = 0 , the Laplacian energy is defined as L E = ∑ i = 1 n | μ i − 2 m / n | . Let σ be the largest positive integer such that μ σ ≥ 2 m / n . We characterize the graphs satisfying σ = n − 1 . Using this, we obtain lower bounds for LE in terms of n, m , and the first Zagreb index. In addition, we present some upper bounds for LE in terms of graph invariants such as n, m , maximum degree, vertex cover number, and spanning tree packing number. [ABSTRACT FROM AUTHOR]

We determine the unique graphs with minimum distance Laplacian spectral radius among connected graphs with fixed number of pendent vertices, the unique trees with minimum distance Laplacian spectral radius among trees with fixed bipartition, the unique graphs with minimum distance Laplacian spectral radius among graphs with fixed edge connectivity at most half of the number of vertices. We also discuss the minimum distance Laplacian spectral radius of graphs with fixed connectivity. For k = 1 , … , ⌊ n − 2 2 ⌋ , we determine the unique n -vertex tree with the ( k + 1 ) -th smallest distance Laplacian spectral radius. [ABSTRACT FROM AUTHOR]

The Harary index of a graph is defined as the sum of reciprocals of distances between all pairs of vertices of the graph. In this paper we provide an upper bound of the Harary index in terms of the vertex or edge connectivity of a graph. We characterize the unique graph with the maximum Harary index among all graphs with a given number of cut vertices or vertex connectivity or edge connectivity. In addition we also characterize the extremal graphs with the second maximum Harary index among all graphs with given vertex connectivity. [ABSTRACT FROM AUTHOR]

Abstract: The transmission of a connected graph is the sum of all distances between all pairs of vertices in , it is also called the Wiener index of . In this paper, sharp bounds on the transmission are determined for several classes of connected bipartite graphs. For example, in the class of all connected -vertex bipartite graphs with a given matching number , the minimum transmission is realized only by the graph ; in the class of all connected -vertex bipartite graphs of diameter , the extremal graphs with the minimal transmission are characterized. Moreover, all the extremal graphs having the minimal transmission in the class of all connected -vertex bipartite graphs with a given vertex connectivity (resp. edge-connectivity) are also identified. [Copyright &y& Elsevier]

Abstract: Let and be the maximum number of edge-disjoint spanning trees and the second largest eigenvalue of a graph G, respectively. Motivated by a question of Seymour on the relationship between eigenvalues of a graph G and , Cioabă and Wong conjectured that for any integers , and a d-regular graph G, if , then . They proved this conjecture for . Gu, Lai, Li and Yao generalized this conjecture to simple graph and conjectured that for any integer and a graph G with minimum degree δ and maximum degree Δ, if then . In this paper, we prove that implies and show the two conjectures hold for sufficiently large n. [Copyright &y& Elsevier]

Abstract: The direct product of graphs and is the graph, denoted as , with vertex set , where vertices and are adjacent in if and . The edge connectivity of a graph , denoted as , is the size of a minimum edge-cut in . We introduce a function and prove the following formula We also describe the structure of every minimum edge-cut in . [Copyright &y& Elsevier]

Abstract: Thomassen conjectured that every 4-connected line graph is Hamiltonian. Chen and Lai [Z.-H. Chen, H.-J. Lai, Reduction techniques for super-Eulerian graphs and related topics—an update, in: Ku Tung-Hsin (Ed.), Combinatorics and Graph Theory, vol. 95, World Scientific, Singapore/London, 1995, pp. 53–69, Conjecture 8.6] conjectured that every 3-edge connected, essentially 6-edge connected graph is collapsible. In this paper, we prove the following results. (1) Every 3-edge connected, essentially 6-edge connected graph with edge-degree at least 7 is collapsible. (2) Every 3-edge connected, essentially 5-edge connected graph with edge-degree at least 6 and at most 24 vertices of degree 3 is collapsible which implies that 5-connected line graph with minimum degree at least 6 of a graph with at most 24 vertices of degree 3 is Hamiltonian. (3) Every 3-connected, essentially 11-connected line graph is Hamilton-connected which strengthens the result in [H.-J. Lai, Y. Shao, H. Wu, J. Zhou, Every 3-connected, essentially 11-connected line graph is Hamiltonian, J. Combin. Theory, Ser. B 96 (2006) 571–576] by Lai et al. (4) Every 7-connected line graph is Hamiltonian connected which is proved by a method different from Zhan’s. By using the multigraph closure introduced by Ryjáček and Vrána which turns a claw-free graph into the line graph of a multigraph while preserving its Hamilton-connectedness, the results (3) and (4) can be extended to claw-free graphs. [Copyright &y& Elsevier]

Abstract: Let denote the distance matrix of a strongly connected digraph . The largest eigenvalue of is called the distance spectral radius of a digraph , denoted by . Recently, many studies proposed the use of as a molecular structure description of alkanes. In this paper, we characterize the extremal digraphs with minimum distance spectral radius among all digraphs with given vertex connectivity and the extremal graphs with minimum distance spectral radius among all graphs with given edge connectivity. Moreover, we give the exact value of the distance spectral radius of those extremal digraphs and graphs. We also characterize the graphs with the maximum distance spectral radius among all graphs of fixed order with given vertex connectivity 1 and 2. [Copyright &y& Elsevier]

Abstract: For a graph G with eigenvalues , its Estrada index is defined as . We determine the unique graphs with maximum Estrada indices among graphs with given number of cut vertices, connectivity, and edge connectivity, respectively. [Copyright &y& Elsevier]

Abstract: A -container of between and , , is a set of internally disjoint paths between and . A -container of is a -container if it contains all vertices of . A graph is -connected if there exists a -container between any two distinct vertices. Thus, every -connected graph is Hamiltonian connected. Moreover, every -connected graph is Hamiltonian. Zhan proved that is Hamiltonian connected if the edge-connectivity of is at least 4. In this paper, we generalize this result by proving is -connected if the edge-connectivity of is at least . We also generalize our result into spanning fan-connectivity. [Copyright &y& Elsevier]

Abstract: This work studies the super edge connectivity and super restricted edge connectivity of direct product graphs, Cartesian product graphs, strong product graphs and lexicographic product graphs. As a result, sufficient conditions for optimizing the edge connectivity and restricted edge connectivity of these graphs are presented. [ABSTRACT FROM AUTHOR]

Abstract: Let be a simple graph with vertex set and edge set . The adjacency matrix of a graph is denoted by and defined as the matrix , where for and 0 otherwise. The largest eigenvalue () of is called the spectral radius or the index of . The Laplacian matrix of is , where is the diagonal matrix of its vertex degrees and is the adjacency matrix. Among all eigenvalues of the Laplacian matrix of a graph, the most studied is the second smallest, called the algebraic connectivity () of a graph [12]. In [1,2], Aouchiche et al. have given a series of conjectures on index () and algebraic connectivity () of (see also [3]). Here we prove two conjectures and disprove one by a counter example. [Copyright &y& Elsevier]

Abstract: It is shown in this work that all n-dimensional hypercube networks for n ⩾4 are maximally 3-restricted edge connected. Employing this observation, we analyze the reliability of hypercube networks and determine the first 3n −5 coefficients of the reliability polynomial of n-cube networks. [Copyright &y& Elsevier]

Abstract: For a (molecular) graph, the first Zagreb index is equal to the sum of squares of the vertex degrees, and the second Zagreb index is equal to the sum of the products of degrees of pairs of adjacent vertices. In this paper, we study the Zagreb indices of graphs of order with (resp. ) and sharp lower and upper bounds are obtained for and for (resp. ), where is the set of graphs of order with , and is the set of graphs of order with . [Copyright &y& Elsevier]

Abstract: In this work we show that among all -vertex graphs with edge or vertex connectivity , the graph , the join of , the complete graph on vertices, with the disjoint union of and , is the unique graph with maximum sum of squares of vertex degrees. This graph is also the unique -vertex graph with edge or vertex connectivity whose hyper-Wiener index is minimum. [Copyright &y& Elsevier]

Abstract: We characterize graphs of large enough order or large enough minimum degree which contain edge cuts whose deletion results in a graph with a specified number of large components. This generalizes and extends recent results due to Ou [Jianping Ou, Edge cuts leaving components of order at least , Discrete Math. 305 (2005), 365–371] and Zhang and Yuan [Z. Zhang, J. Yuan, A proof of an inequality concerning -restricted edge connectivity, Discrete Math. 304 (2005), 128–134]. [Copyright &y& Elsevier]

Abstract: Let be a simple graph and be the adjacency matrix of . The eigenvalues of are those of . In this paper, we characterize the graphs with the minimal least eigenvalue among all graphs of fixed order with given vertex connectivity or edge connectivity. [Copyright &y& Elsevier]

Abstract: k-Restricted edge connectivity is an important parameter in measuring the reliability and fault tolerance of large interconnection networks. In this paper we present two families of graphs similar with the networks proposed by Chen et al. [Y.C. Chen, J.J.M. Tan, L.H. Hsu, S.S. Kao, Super-connectivity and super edge-connectivity for some interconnection networks, Applied Mathematics and Computation 140 (2003) 245–254] and study the -restricted edge connectivity of these graphs. In particular, as the applications of our results, the -restricted edge connectivity of the recursive circulant graphs and the n-ary k-cubes is given. [Copyright &y& Elsevier]

Abstract: An edge cut of a connected graph is 4-restricted if it disconnects this graph with each component having order at least four. The size of minimum 4-restricted edge cuts of graph G is called its 4-restricted edge connectivity and is denoted by . Let , where denotes the number of edges of graph G with exactly one endpoint in F. For connected graphs that contain 4-restricted edge cuts, is proved to be an upper bound on if G has order at least 11. If G is a k-regular vertex-transitive graph of girth at least five, then when . [Copyright &y& Elsevier]

Abstract: Let be the family of graphs with n vertices and m edges, when n and m are previously given. It is well-known that there is a subset of constituted by graphs G such that the vertex connectivity, the edge connectivity, and the minimum degree are all equal. In this paper, S(a, b)-classes of connected (a, b)-linear graphs with n vertices and m edges are described, where m is given as a function of . Some of them have extremal graphs for which the equalities above are extended to algebraic connectivity. These graphs are Laplacian integral although they are not threshold graphs. However, we do build threshold graphs in S(a, b). [Copyright &y& Elsevier]

Abstract: A well known theorem of Whitney states that for any graph G,For any set of positive integers , , we determine the least order and the least size among all graphs with , and . We also show that there exist graphs of all orders greater than or equal to the least order among those graphs with , and . [Copyright &y& Elsevier]

Abstract: Fault tolerant measures have played an important role in the reliability of an interconnection network. Edge connectivity, restricted-edge-connectivity, extra-edge-connectivity and super-edge-connectivity of many well-known interconnection networks have been explored. In this paper, we study the 2-extra-edge connectivity of a special class of graphs G(G 0, G 1; M) proposed by Chen et al. [Appl. Math. Comput. 140 (2003) 245–254]. Then by showing that several well-known interconnection networks such as hypercubes, twisted cubes, crossed cubes and Möbius cubes are all contained in this class. We show that their 2-extra-edge-connectivity are all not less than 3n −4 when their dimension n is not less than 4. That is, when n ⩾4, at least 3n −4 edges are to be removed to get any of an n-dimensional above networks disconnected provided that the removed edges does not isolate a vertex or an edge in the faulty networks. Compared with previous results, our result enhances the fault tolerant ability of above networks theoretically. [Copyright &y& Elsevier]

Abstract: The -path graph corresponding to a graph G has for vertices the set of all paths of length k in G. Two vertices are joined by an edge if and only if the intersection of the corresponding paths forms a path of length in G, and their union forms either a cycle or a path of length . Path graphs were introduced by Broersma and Hoede (J. Graph. Theory 13 (1989) 427) as a generalization of line graphs, because for , path graphs are just line graphs. Results on the edge-connectivity of line graphs are given by Chartrand and Stewart (Math. Ann. 182 (1969) 170), later by Zamfirescu (Math. Ann. 187 (1970) 305), and by Jixiang Meng (Graph Theory Notes of New York XL (2001) 12). The connectivity of -path graphs has been studied by Knor and Niepel (Graph Theory 20 (2000) 181), where they proved a necessary and sufficient condition for the -path graphs to be disconnected, assuming that G has girth of at least . Going one step further, we prove in this work that the edge-connectivity of is at least for a graph G of girth at least and minimum degree . Furthermore, we show provided that . [Copyright &y& Elsevier]

Let G=(V,E) be a k-regular graph with connectivity κ and edge connectivity λ. G is maximum connected if κ=k, and G is maximum edge connected if λ=k. Moreover, G is super-connected if it is a complete graph, or it is maximum connected and every minimum vertex cut is {x|(v,x)∈E} for some vertex v∈V; and G is super-edge-connected if it is maximum edge connected and every minimum edge disconnecting set is {(v,x)|(v,x)∈E} for some vertex v∈V. In this paper, we present three schemes for constructing graphs that are super-connected and super-edge-connected. Applying these construction schemes, we can easily discuss the super-connected property and the super-edge-connected property of hypercubes, twisted cubes, crossed cubes, mo¨bius cubes, split-stars, and recursive circulant graphs. [Copyright &y& Elsevier]

Let G be a connected graph and let X be the set of projective points defined by the column vectors of the incidence matrix of G over a field K of any characteristic. We determine the generalized Hamming weights of the Reed–Muller-type code over the set X in terms of graph theoretic invariants. As an application to coding theory we show that if G is non-bipartite and K is a finite field of char (K) ≠ 2 , then the r th generalized Hamming weight of the linear code generated by the rows of the incidence matrix of G is the r th weak edge biparticity of G. If char (K) = 2 or G is bipartite, we prove that the r th generalized Hamming weight of that code is the r th edge connectivity of G. [ABSTRACT FROM AUTHOR]