A note on locally connected and hamiltonian-connected graphs

A graphG is locallyn-connected,n≧1, if the subgraph induced by the neighborhood of each vertex isn-connected. It is shown that every connected, locally 3-connected graph containing no induced subgraph isomorphic toK(1, 3) is hamiltonian-connected.     

Every 3-connected,locally connected,claw-free graph is Hamilton-connected

A graph G is locally connected if the subgraph induced by the neighbourhood of each vertex is connected. We prove that a locally connected graph G of order p ≥ 4, containing no induced subgraph isomorphic to K_1,3, is Hamilton-connected if and only if G is 3-connected. © 1996 John Wiley & Sons, Inc.     

Vertices of Degree 5 in a Contraction Critically 5-connected Graph

An edge of a k-connected graph is said to be k-contractible if the contraction of the edge results in a k-connected graph. A k-connected graph with no k-contractible edge is said to be contraction critically k-connected. We prove that a contraction critically 5-connected graph on n vertices has at least n/5 vertices of degree 5. We also show that, for a graph G and an integer k greater than 4, there exists a contraction critically k-connected graph which has G as its induced subgraph.     

Long cycles and spanning subgraphs of locally maximal 1-planar graphs

A graph is 1-planar if it has a drawing in the plane such that each edge is crossed at most once by another edge. Moreover, if this drawing has the additional property that for each crossing of two edges the end vertices of these edges induce a complete subgraph, then the graph is locally maximal 1-planar. For a 3-connected locally maximal 1-planar graph G, we show the existence of a spanning 3-connected planar subgraph and prove that G is Hamiltonian if G has at most three 3-vertex-cuts, and that G is traceable if G has at most four 3-vertex-cuts. Moreover, infinitely many nontraceable 5-connected 1-planar graphs are presented.     

局部连通图的群Z_3-连通性

本文研究了局部连通图的群连通性的问题.利用不断收缩非平凡Z_3-连通子图的方法,在G是3-边连通且局部连通的无爪无沙漏图的情况下,获得了G不是群Z_3-连通的当且仅当G是K_4或W_5.推广了当G是2-边连通且局部3-边连通时,G是群Z_3-连通的这个结果.     

Local connectivity of a random graph

A graph is locally connected if for each vertex ν of degree ≧2, the subgraph induced by the vertices adjacent to ν is connected. In this paper we establish a sharp threshold function for local connectivity. Specifically, if the probability of an edge of a labeled graph of order n is p = ((3/2 +?_n) log n/n)^1/2 where ?_n = (log log n + log(3/8) + 2x)/(2 log n), then the limiting probability that a random graph is locally connected is exp(-exp(-x)).     

Every connected,locally connected nontrivial graph with no induced claw is hamiltonian

A graph is locally connected if every neighborthood induces a connected subgraph. We show here that every connected, locally connected graph on p ≥ 3 vertices and having no induced K_1,3 is Hamiltonian. Several sufficient conditions for a line graph to be Hamiltonian are obtained as corollaries.     

Connectivity,graph minors,and subgraph multiplicity

It is well known that any planar graph contains at most O(n) complete subgraphs. We extend this to an exact characterization: G occurs O(n) times as a subgraph of any planar graph, if and only if G is three-connected. We generalize these results to similarly characterize certain other minor-closed families of graphs; in particular, G occurs O(n) times as a subgraph of the K_b,c-free graphs, b ≥ c and c ≤ 4, iff G is c-connected. Our results use a simple Ramsey-theoretic lemma that may be of independent interest. © 1993 John Wiley & Sons, Inc.     

On 2-Connected Spanning Subgraphs with Bounded Degree in K 1,r -Free Graphs

For any integer r > 1, an r-trestle of a graph G is a 2-connected spanning subgraph F with maximum degree Δ(F) ≤ r. A graph G is called K _1,r -free if G has no K _1,r as an induced subgraph. Inspired by the work of Ryjáček and Tkáč, we show that every 2-connected K _1,r -free graph has an r-trestle. The paper concludes with a corollary of this result for the existence of k-walks.     

Subdivisions in apex graphs

The Kelmans-Seymour conjecture states that every 5-connected nonplanar graph contains a subdivided K ₅. Certain questions of Mader propose a “plan” towards a possible resolution of this conjecture. One part of this plan is to show that every 5-connected nonplanar graph containing K^-₄K^{-}_{4} or K _2,3 as a subgraph has a subdivided K ₅. Recently, Ma and Yu showed that every 5-connected nonplanar graph containing K^-₄K^{-}_{4} as a subgraph has a subdivided K ₅. We take interest in K _2,3 and prove that every 5-connected nonplanar apex graph containing K _2,3 as a subgraph contains a subdivided K ₅. The result of Ma and Yu can be used in a short discharging argument to prove that every 5-connected nonplanar apex graph contains a subdivided K ₅; here we propose a longer proof whose merit is that it avoids the use of discharging and employs a more structural approach; consequently it is more amenable to generalization.     

A characterization of Hamiltonian prisms

A characterization is established for a graph G to have a Hamilton cycle in G × K₂, the prism over G. Moreover, it is shown that every 3-connected graph has a 2-connected spanning bipartite subgraph. Using this result, the existence of a Hamilton cycle in the prism over every 3-connected cubic graph is established. Further, the existence of a Hamilton cycle in the prism over a cubic 2-connected graph is also discussed. Earlier results in this direction are shown to be particular cases of the results obtained here. © 1993 John Wiley & Sons, Inc.     

On extremal sizes of locally k-tree graphs

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k ⩾ 0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k ⩾ 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between Ω(n) and O(n ²), where both bounds are asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.     

Hamiltonian connected hourglass free line graphs

Thomassen [Reflections on graph theory, J. Graph Theory 10 (1986) 309-324] conjectured that every 4-connected line graph is hamiltonian. An hourglass is a graph isomorphic to K₅-E(C₄), where C₄ is a cycle of length 4 in K₅. In Broersma et al. [On factors of 4-connected claw-free graphs, J. Graph Theory 37 (2001) 125-136], it is shown that every 4-connected line graph without an induced subgraph isomorphic to the hourglass is hamiltonian connected. In this note, we prove that every 3-connected, essentially 4-connected hourglass free line graph, is hamiltonian connected.     

Contractible Triples in Highly Connected Graphs

We prove that if G is k-connected (with k ≥ 2), then G contains either a cycle of length 4 or a connected subgraph of order 3 whose contraction results in a k-connected graph. This immediately implies that any k-connected graph has either a cycle of length 4 or a connected subgraph of order 3 whose deletion results in a (k − 1)-connected graph.     

A remark on regularization in Hilbert spaces

Every graph with uncountable chromatic number contains for every finiten ann-connected subgraph with infinite degrees which has uncountable chromatic number.     

Greatest common subgraphs with specified properties

A graphG without isolated vertices is a greatest common subgraph of a setG of graphs, all having the same size, ifG is a graph of maximum size that is isomorphic to a subgraph of every graph inG. A number of results concerning greatest common subgraphs are presented. For several graphical propertiesP, we discuss the problem of determining, for a given graphG with propertyP, the existence of two non-isomorphic graphsG ₁ andG ₂ of equal size, also with propertyP, such thatG is the unique greatest common subgraph ofG ₁ andG ₂. In particular, this problem is solved whenP is the property of being 2-connected and whenP is the property of having chromatic numbern.     

A necessary and sufficient condition for connected,locally k-connected k1,3-free graphs to be k-hamiltonian

We prove the following conjecture of Broersma and Veldman: A connected, locally k-connected K_1,3-free graph is k-hamiltonian if and only if it is (k + 2)-connected (K ? 1).     

Counting 1-factors in infinite graphs

F. Bry (J. Combin. Theory Ser. B 34 (1983), 48–57) proved that a locally finite infinite n-connected factorizable graph has at least (n−1)! 1-factors and showed that for n = 2 this lower bound is sharp. We prove that for n≥3 any infinite n-connected factorizable graph has at least n! 1-factors (which is a sharp lower bound).     

The contractible subgraph of 5-connected graphs

An edge e of a k-connected graph G is said to be k-removable if G — e is still k-connected. A subgraph H of a k-connected graph is said to be k-contractible if its contraction results still in a k-connected graph. A k-connected graph with neither removable edge nor contractible subgraph is said to be minor minimally k-connected. In this paper, we show that there is a contractible subgraph in a 5-connected graph which contains a vertex who is not contained in any triangles. Hence, every vertex of minor minimally 5-connected graph is contained in some triangle.     

Orthogonal Polarity Graphs and Sidon Sets

Determining the maximum number of edges in an n‐vertex C₄‐free graph is a well‐studied problem that dates back to a paper of Erd?s from 1938. One of the most important families of C₄‐free graphs are the Erd?s‐Rényi orthogonal polarity graphs. We show that the Cayley sum graph constructed using a Bose‐Chowla Sidon set is isomorphic to a large induced subgraph of the Erd?s‐Rényi orthogonal polarity graph. Using this isomorphism, we prove that the Petersen graph is a subgraph of every sufficiently large Erd?s‐Rényi orthogonal polarity graph.