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.     

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.     

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.     

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

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

Nowhere‐zero 3‐flows in locally connected graphs

Let G be a graph. For each vertex v ∈V(G), N_v denotes the subgraph induces by the vertices adjacent to v in G. The graph G is locally k‐edge‐connected if for each vertex v ∈V(G), N_v is k‐edge‐connected. In this paper we study the existence of nowhere‐zero 3‐flows in locally k‐edge‐connected graphs. In particular, we show that every 2‐edge‐connected, locally 3‐edge‐connected graph admits a nowhere‐zero 3‐flow. This result is best possible in the sense that there exists an infinite family of 2‐edge‐connected, locally 2‐edge‐connected graphs each of which does not have a 3‐NZF. © 2003 Wiley Periodicals, Inc. J Graph Theory 42: 211–219, 2003     

Global cycle properties in graphs with large minimum clustering coefficient

Let 𝒫 be a graph property. A graph G is said to be locally 𝒫 (closed locally 𝒫) if the subgraph induced by the open neighbourhood (closed neighbourhood, respectively) of every vertex in G has property 𝒫. The clustering coefficient of a vertex is the proportion of pairs of its neighbours that are themselves neighbours. The minimum clustering coefficient of G is the smallest clustering coefficient among all vertices of G. Let H be a subgraph of a graph G and let S ? V (H). We say that H is a strongly induced subgraph of G with attachment set S, if H is an induced subgraph of G and the vertices of V (H) ? S are not incident with edges that are not in H. A graph G is fully cycle extendable if every vertex of G lies in a triangle and for every nonhamiltonian cycle C of G, there is a cycle of length |V (C)|?+?1 that contains the vertices of C. A complete characterization, of those locally connected graphs with minimum clustering coefficient 1/2 and maximum degree at most 6 that are fully cycle extendable, is given in terms of forbidden strongly induced subgraphs (with specified attachment sets). Moreover, it is shown that all locally connected graphs with Δ?≤?6 and sufficiently large minimum clustering coefficient are weakly pancylic, thereby proving Ryj´ǎcek’s conjecture for this class of graphs.     

Compatible connectedness in graphs and topological spaces

A topology on the vertex set of a graphG iscompatible with the graph if every induced subgraph ofG is connected if and only if its vertex set is topologically connected. In the case of locally finite graphs with a finite number of components, it was shown in [11] that a compatible topology exists if and only if the graph is a comparability graph and that all such topologies are Alexandroff. The main results of Section 1 extend these results to a much wider class of graphs. In Section 2, we obtain sufficient conditions on a graph under which all the compatible topologies are Alexandroff and in the case of bipartite graphs we show that this condition is also necessary.     

A characterization of graphs without long induced paths

In a connected graph define the k-center as the set of vertices whose distance from any other vertex is at most k. We say that a vertex set S d-dominates G if for every vertex x there is a y ∈ S whose distance from x is at most d. Call a graph P_t-free if it does not contain a path on t vertices as an induced subgraph. We prove that a connected graph is P_2k-1-free (P_2k-free) if and only if each of its connected induced subgraphs H satisfy the following property: The k-center of H (k - 1)-dominates ((k - 2)-dominates) H. Moreover, we show that the subgraph induced by the (t - 3)-center in any P_t-free connected graph is again connected and has diameter at most t - 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)).     

Almost claw-free graphs

We say that G is almost claw-free if the vertices that are centers of induced claws (K_1,3) in G are independent and their neighborhoods are 2-dominated. Clearly, every claw-free graph is almost claw-free. It is shown that (i) every even connected almost claw-free graph has a perfect matching and (ii) every nontrivial locally connected K_1,4-free almost claw-free graph is fully cycle extendable.     

A characterization of radius-critical graphs

A graph G is radius-critical if every proper induced connected subgraph of G has radius strictly smaller than the original graph. Our main purpose is to characterize all such graphs.     

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.     

Some sufficient conditions for the existence of a 1-factor

The following theorem is proved: Let G be a graph of even order. Assume that there exists a connected spanning subgraph F of G such that for every set U of four vertices in G, if the subgraph of F induced by U is a star, then the subgraph of G induced by U is complete. Then G has a 1-factor. The above theorem is derived from another sufficient condition for the existence of a 1-factor, which is also proved in this paper (Lemma 1).     

Connected Domination Stable Graphs Upon Edge Addition

Abstract

A set S of vertices in a graph G is a connected dominating set of G if S dominates G and the subgraph induced by S is connected. We study the graphs for which adding any edge does not change the connected domination number.     

Minimal configuration trees

A graph is singular of nullity η if zero is an eigenvalue of its adjacency matrix with multiplicity η. If η(G)=1, then the core of G is the subgraph induced by the vertices associated with the non-zero entries of the zero-eigenvector. A connected subgraph of G with the least number of vertices and edges, that has nullity one and the same core as G, is called a minimal configuration. A subdivision of a graph G is obtained by inserting a vertex on every edge of G. We review various properties of minimal configurations. In particular, we show that a minimal configuration is a tree if and only if it is a subdivision of some other tree.     

Retracts of hypercubes

An induced subgraph G of a graph H is a retract of H if there is an edge-preserving map f from H onto G such that f|_G is the identity map on G. A median graph is a connected graph such that for any three vertices u,v and w, there exists a unique vertex x which lies simultaneously on some shortest (u,v)-, (v,w)-, and (w,u)-paths. It is shown that a graph G is a retract of some hypercube if and only if G is a median graph.     

F-Continuous Graphs

For a nontrivial connected graph F, the F-degree of a vertex in a graph G is the number of copies of F in G containing . A graph G is F-continuous (or F-degree continuous) if the F-degrees of every two adjacent vertices of G differ by at most 1. All P₃-continuous graphs are determined. It is observed that if G is a nontrivial connected graph that is F-continuous for all nontrivial connected graphs F, then either G is regular or G is a path. In the case of a 2-connected graph F, however, there always exists a regular graph that is not F-continuous. It is also shown that for every graph H and every 2-connected graph F, there exists an F-continuous graph G containing H as an induced subgraph.     

Reconstruction of locally finite connected graphs with at least three infinite wings

Let G be a locally finite connected graph that can be expressed as the union of a finite subgraph and p disjoint infinite subgraphs, where 3 ≦ p < ∞, but cannot be expressed as the union of a finite subgraph and p + 1 disjoint infinite subgraphs. Then G is reconstructible.     

Hereditarily extended properties, quasi-random graphs and not necessarily induced subgraphs

Recently much attention has been focused on the theory of quasi-random graph and hypergraph properties. The class of quasi-random graphs is defined by certain equivalent graph properties possessed by random graphs. We shall investigate propertiesP which do not imply quasi-randomnes for sequences (G _n ) of graphs on their own, but do imply if they hold not only for the whole graphG _n but also for every sufficiently large subgraph ofG _n . Here the properties are strongly connected to countingnot necessarily induced subgraphs of a given type, while in a subsequent paper we shall investigate the properties connected with counting induced subgraphs.Dedicated to the memory of Paul ErdsResearch supported by OTKA N1909.     

A generalization of line graphs: (X,Y)-intersection graphs

Given a pair (X, Y) of fixed graphs X and Y, the (X, Y)-intersection graph of a graph G is a graph whose vertices correspond to distinct induced subgraphs of G that are isomorphic to Y, and where two vertices are adjacent iff the intersection of their corresponding subgraphs contains an induced subgraph isomorphic to X. This generalizes the notion of line graphs, since the line graph of G is precisely the (K₁, K₂)-intersection graph of G. In this paper, we consider the forbidden induced subgraph characterization of (X, Y)-intersection graphs for various (X, Y) pairs; such consideration is motivated by the characterization of line graphs through forbidden induced subgraphs. For this purpose, we restrict our attention to hereditary pairs (a pair (X, Y) is hereditary if every induced subgraph of any (X, Y)-intersection graph is also an (X, Y)-intersection graph), since only for such pairs do (X, Y)-intersection graphs have forbidden induced subgraph characterizations. We show that for hereditary 2-pairs (a pair (X, Y) is a 2-pair if Y contains exactly two induced subgraphs isomorphic to X), the family of line graphs of multigraphs and the family of line graphs of bipartite graphs are the maximum and minimum elements, respectively, of the poset on all families of (X, Y)-intersection graphs ordered by set inclusion. We characterize 2-pairs for which the family of (X, Y)-intersection graphs are exactly the family of line graphs or the family of line graphs of multigraphs. © 1996 John Wiley & Sons, Inc.