Search

In this paper, we characterize connected $$\{K_{1,3},N(2,1,0)\}$$ -free but not $$N(1,1,1)$$ -free graphs. By combining our result and a theorem showed by Duffus et al. (every $$2$$ -connected $$\{K_{1,3},N(1,1,1)\}$$ -free graph is Hamiltonian), we give an alternative proof of Bedrossian's theorem (every $$2$$ -connected $$\{K_{1,3},N(2,1,0)\}$$ -free graph is Hamiltonian). [ABSTRACT FROM AUTHOR]

We show that there is a well-defined family of connected simple graphs Λ( n, m) on n vertices and m edges such that all graphs in Λ( n, m) have the same number of spanning trees, and if $${G \in \Lambda(n, m)}$$ then the number of spanning trees in G is strictly less than the number of spanning trees in any other connected simple graph $${H, H \notin \Lambda(n, m)}$$ , on n vertices and m edges. [ABSTRACT FROM AUTHOR]

An edge cut of a connected graph is 5-restricted if its removal leaves every component having order at least five. Graphs that contain 5-restricted edge cuts are characterized in this paper. As a result, it is shown that a connected graph G of order at least 13 contains 5-restricted edge cuts if and only if $${G \setminus v}$$ contains a component of order at least five for every vertex v of graph G. [ABSTRACT FROM AUTHOR]

An edge-colored graph G is rainbow connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection number of a connected graph G, denoted by rc( G), is the smallest number of colors that are needed in order to make G rainbow connected. In this paper, we proved that rc( G) ≤ 3( n + 1)/5 for all 3-connected graphs. [ABSTRACT FROM AUTHOR]

In 1966 T. Gallai asked whether connected graphs with empty intersection of their longest paths do or do not exist. After examples of such graphs were found, the question was extended to graphs of higher connectivity, and to cycles instead of paths. Examples being again found, for connectivity up to 3, the question has been asked whether there exist large families of graphs without Gallai's property. The family of grid graphs, a special kind of graphs embedded in the planar square lattice $${\mathcal {L}}$$ , has been shown by B. Menke to contain no graph enjoying Gallai's property. In this paper we find several examples of graphs embedded in $${\mathcal {L}}$$ and enjoying that property with respect to both paths and cycles. [ABSTRACT FROM AUTHOR]

The classic lower bounds δ + 1 (Dirac), 2 δ (Dirac) and 3 δ − 3 (Voss and Zuluaga) for the circumference (the order of a longest cycle C in a graph G) are based on the minimum degree δ and some G\ C structures, combined with some additional connectivity conditions. A natural problem arises to find an analogous bound in a general form ( i + 1)( δ − i + 1) with i = 0, 1, . . . , δ, including the bounds δ + 1, 2 δ and 3 δ − 3 as special cases. In this paper we present two tight lower bounds for the circumference just of the form ( i + 1)( δ − i + 1) for each $${i\in\{0,\ldots,\delta\}}$$ based entirely on appropriate G\ C structures, actually escaping any other additional conditions: in each graph G, (i) $${|C|\geq(\overline{p}+1)(\delta-\overline{p}+1)}$$ and (ii) $${|C|\geq(\overline{c}+1)(\delta-\overline{c}+1),}$$ where $${\overline{p}}$$ and $${\overline{c}}$$ denote the orders of a longest path and a longest cycle in G\ C, respectively. [ABSTRACT FROM AUTHOR]

Let G be a graph. We denote p( G) and c( G) the order of a longest path and the order of a longest cycle of G, respectively. Let κ( G) be the connectivity of G, and let σ( G) be the minimum degree sum of an independent set of three vertices in G. In this paper, we prove that if G is a 2-connected graph with p( G) − c( G) ≥ 2, then either (i) c( G) ≥ σ( G) − 3 or (ii) κ( G) = 2 and p( G) ≥ σ( G) − 1. This result implies several known results as corollaries and gives a new lower bound of the circumference. [ABSTRACT FROM AUTHOR]

The subdivision graph S( Σ) of a connected graph Σ is constructed by adding a vertex in the middle of each edge. In a previous paper written with Cheryl E. Praeger, we characterised the graphs Σ such that S( Σ) is locally ( G, s)-distance transitive for s ≤ 2 diam( Σ) − 1 and some G ≤ Aut( Σ). In this paper, we solve the remaining cases by classifying all the graphs Σ such that S( Σ) is locally ( G, s)-distance transitive for some s ≥ 2 diam( Σ) and some G ≤ Aut( Σ). As a corollary, we get a classification of all the graphs whose subdivision graph is locally distance transitive. [ABSTRACT FROM AUTHOR]

Given a graph G, the m-step graph of G, denoted by S( G), has the same vertex set as G and an edge between two distinct vertices u and v if there is a walk of length m from u to v. The line graph of G, denoted by L( G), is a graph such that the vertex set of L( G) is the edge set of G and two vertices u and v of L( G) are adjacent if the edges corresponding to u and v share a common end vertex in G. We characterize connected graphs G such that S( G) and L( G) are isomorphic. [ABSTRACT FROM AUTHOR]

We discuss the range of values for the integrity of a graphs G( n, k) where G( n, k) denotes a simple graph with n vertices and k edges. Let I( n, k) and I( n, k) be the maximal and minimal value for the integrity of all possible G( n, k) graphs and let the difference be D( n, k) = I( n, k) − I( n, k). In this paper we give some exact values and several lower bounds of D( n, k) for various values of n and k. For some special values of n and for s < n we construct examples of graphs G = G( n, n + s) with a maximal integrity of I( G) = I( C) + s where C is the cycle with n vertices. We show that for k = n/6 the value of D( n, n/6) is at least $${\frac{\sqrt{6}-1}{3}n}$$ for large n. [ABSTRACT FROM AUTHOR]

( δ, g)-cage is a δ-regular graph with girth g and with the least possible number of vertices. In this paper, we show that all ( δ, g)-cages with odd girth g ≥ 9 are r-connected, where ( r − 1) ≤ δ + $ \sqrt \delta $ − 2 < r and all ( δ, g)-cages with even girth g ≥ 10 are r-connected, where r is the largest integer satisfying $ \frac{{r\left( {r - 1} \right)^2 }} {4} + 1 + 2r\left( {r - 1} \right) \leqslant \delta $. These results support a conjecture of Fu, Huang and Rodger that all ( δ, g)-cages are δ-connected. [ABSTRACT FROM AUTHOR]

Let G be a connected graph of order n. The diameter of a graph is the maximum distance between any two vertices of G. In this paper, we will give some bounds on the diameter of G in terms of eigenvalues of adjacency matrix and Laplacian matrix, respectively. [ABSTRACT FROM AUTHOR]