3-Connected line graphs of triangular graphs are panconnected and 1-hamiltonian

A graph is k-triangular if each edge is in at least k triangles. Triangular is a synonym for 1-triangular. It is shown that the line graph of a triangular graph of order at least 4 is panconnected if and only if it is 3-connected. Furthermore, the line graph of a k-triangular graph is k-hamiltonian if and only if it is (k + 2)-connected (k ? 1). These results generalize work of Clark and Wormald and of Lesniak-Foster. Related results are due to Oberly and Sumner and to Kanetkar and Rao.     

Pancyclic oriented graphs

Let D be an oriented graph of order n ≧ 9 and minimum degree n ? 2. This paper proves that D is pancyclic if for any two vertices u and v, either uv ? A(D), or d_D⁺(u) + d_D^?(v) ≧ n ? 3.     

Pancyclic graphs and linear forests

Given integers k,s,t with 0≤s≤t and k≥0, a (k,t,s)-linear forest F is a graph that is the vertex disjoint union of t paths with a total of k edges and with s of the paths being single vertices. If the number of single vertex paths is not critical, the forest F will simply be called a (k,t)-linear forest. A graph G of order n≥k+t is (k,t)-hamiltonian if for any (k,t)-linear forest F there is a hamiltonian cycle containing F. More generally, given integers m and n with k+t≤m≤n, a graph G of order n is (k,t,s,m)-pancyclic if for any (k,t,s)-linear forest F and for each integer r with m≤r≤n, there is a cycle of length r containing the linear forest F. Minimum degree conditions and minimum sum of degree conditions of nonadjacent vertices that imply that a graph is (k,t,s,m)-pancyclic (or just (k,t,m)-pancyclic) are proved.     

Pancyclic subgraphs of random graphs

An n‐vertex graph is called pancyclic if it contains a cycle of length t for all 3≤t≤n. In this article, we study pancyclicity of random graphs in the context of resilience, and prove that if p>n^?1/2, then the random graph G(n, p) a.a.s. satisfies the following property: Every Hamiltonian subgraph of G(n, p) with more than edges is pancyclic. This result is best possible in two ways. First, the range of p is asymptotically tight; second, the proportion of edges cannot be reduced. Our theorem extends a classical theorem of Bondy, and is closely related to a recent work of Krivelevich et al. The proof uses a recent result of Schacht (also independently obtained by Conlon and Gowers). © 2011 Wiley Periodicals, Inc.     

A characterization of panconnected graphs satisfying a local ore-type condition

It is well known that a graph G of order p ≥ 3 is Hamilton-connected if d(u) + d(v) ≥ p + 1 for each pair of nonadjacent vertices u and v. In this paper we consider connected graphs G of order at least 3 for which d(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| + 1 for any path uwv with uv ∉ E(G), where N(x) denote the neighborhood of a vertex x. We prove that a graph G satisfying this condition has the following properties: (a) For each pair of nonadjacent vertices x, y of G and for each integer k, d(x, y) ≤ k ≤ |V(G)| − 1, there is an x − y path of length k. (b) For each edge xy of G and for each integer k (excepting maybe one k η {3,4}) there is a cycle of length k containing xy. Consequently G is panconnected (and also edge pancyclic) if and only if each edge of G belongs to a triangle and a quadrangle. Our results imply some results of Williamson, Faudree, and Schelp. © 1996 John Wiley & Sons, Inc.     

Some panconnected and pancyclic properties of graphs with a local ore-type condition

Asratian and Khachatrian proved that a connected graphG of order at least 3 is hamiltonian ifd(u) + d(v) ≥ |N(u) ∪ N(v) ∪ N(w)| for any pathuwv withuv ? E(G), whereN(x) is the neighborhood of a vertexx. We prove that a graphG with this condition, which is not complete bipartite, has the following properties:

1. For each pair of verticesx, y with distanced(x, y) ≥ 3 and for each integern, d(x, y) ≤ n ≤ |V(G)| ? 1, there is anx ? y path of lengthn.
2. For each edgee which does not lie on a triangle and for eachn, 4 ≤ n ≤ |V(G)|, there is a cycle of lengthn containinge.
3. Each vertex ofG lies on a cycle of every length from 4 to |V(G)|.

This implies thatG is vertex pancyclic if and only if each vertex ofG lies on a triangle.     

Pancyclic graphs and a conjecture of Bondy and Chvátal

A p-vertex graph is called pancyclic if it contains cycles of every length l, 3 ≤ l ≤ p. In this paper we prove the following conjecture of Bondy and Chvátal: If a graph G has vertex degree sequence d₁ ≤ d₂ ≤ … ≤ d_ν, and if $\text{d}{}_{\mathrm{k}}\text{≤ k <}\text{p}\text{2}$ implies d_ν?k ≥ p ? k, then G is pancyclic or bipartite.     

Connected,locally 2-connected,K1,3-free graphs are panconnected

A graph G is locally n-connected, n ≥ 1, if the subgraph induced by the neighborhood of each vertex is n-connected. We prove that every connected, locally 2-connected graph containing no induced subgraph isomorphic to K_1,3 is panconnected.     

Collapsible graphs and reductions of line graphs

A graph G is collapsible if for every even subset X⊆V(G), G has a subgraph Γ such that G−E(Γ) is connected and the set of odd-degree vertices of Γ is X. A graph obtained by contracting all the non-trivial collapsible subgraphs of G is called the reduction of G. In this paper, we characterize graphs of diameter two in terms of collapsible subgraphs and investigate the relationship between the line graph of the reduction and the reduction of the line graph. Our results extend former results in [H.-J. Lai, Reduced graph of diameter two, J. Graph Theory 14 (1) (1990) 77-87], and in [P.A. Catlin, Iqblunnisa, T.N. Janakiraman, N. Srinivasan, Hamilton cycles and closed trails in iterated line graphs, J. Graph Theory 14 (1990) 347-364].     

Graph equations for line graphs and total graphs

All pairs (G,H) of graphs G,H satisfying L(G) = T(H) are determined. The “graph equation“ $\text{L(G)}\text{= T(H)}$ is also solved.     

图和线图的谱性质

Let G be a simple connected graph with n vertices and m edges,Lo be the line graph of G and λ1(LG)≥λ2 (LG)≥...≥λm(LG) be the eigenvalues of the graph LG,.. In this paper, the range of eigenvalues of a line graph is considered. Some sharp upper bounds and sharp lower bounds of the eigenvalues of Lc. are obtained. In oarticular,it is oroved that-2cos(π/n)≤λn-1(LG)≤n-4 and λn(LG)=-2 if and only if G is bipartite.     

Hamiltonian line graphs

Sufficient conditions on the degrees of a graph are given in order that its line graph have a hamiltonian cycle.     

Interval line graphs

We characterize the graphs whose line graphs are interval graphs.     

Generalized line graphs

Generalized line graphs extend the ideas of both line graphs and cocktail party graphs. They were originally motivated by spectral considerations. in this paper several (nonspectral) classical theorems about line graphs are extended to generalized line graphs, including the derivation and construction of the 31 minimal nongeneralized line graphs, a Krausz-type covering characterization, and Whitney-type theorems on isomorphisms and automorphisms.     

Contractions and hamiltonian line graphs

Using the contraction method, we find a best possible condition involving the minimum degree for a triangle-free graph to have a spanning eulerian subgraph.