Paley graphs satisfy all first-order adjacency axioms

A graph satisfies Axiom n if, for any sequence of 2n of its points, there is another point adjacent to the first n and not to any of the last n. We show that, for each n, all sufficiently large Paley graphs satisfy Axiom n. From this we conclude at once that several properties of graphs are not first order, including self-complementarity and regularity.     

k-ordered Hamiltonian graphs

A hamiltonian graph G of order n is k-ordered, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices of G, there exists a hamiltonian cycle that encounters v₁, v₂, …, v_k in this order. Theorems by Dirac and Ore, presenting sufficient conditions for a graph to be hamiltonian, are generalized to k-ordered hamiltonian graphs. The existence of k-ordered graphs with small maximum degree is investigated; in particular, a family of 4-regular 4-ordered graphs is described. A graph G of order n ≥ 3 is k-hamiltonian-connected, 2 ≤ k ≤ n, if for every sequence v₁, v₂, …, v_k of k distinct vertices, G contains a v₁-v_k hamiltonian path that encounters v₁, v₂,…, v_k in this order. It is shown that for k ≥ 3, every (k + 1)-hamiltonian-connected graph is k-ordered and a result of Ore on hamiltonian-connected graphs is generalized to k-hamiltonian-connected graphs. © 1997 John Wiley & Sons, Inc.     

Survey of Double Vertex Graphs

 Let G be a (V,E) graph of order p≥2. The double vertex graph U ₂ (G) is the graph whose vertex set consists of all 2-subsets of V such that two distinct vertices {x,y} and {u,v} are adjacent if and only if |{x,y}∩{u,v}|=1 and if x=u, then y and v are adjacent in G. For this class of graphs we discuss the regularity, eulerian, hamiltonian, and bipartite properties of these graphs. A generalization of this concept is n-tuple vertex graphs, defined in a manner similar to double vertex graphs. We also review several recent results for n-tuple vertex graphs. Received: October, 2001 Final version received: September 20, 2002 Dedicated to Frank Harary on the occasion of his Eightieth Birthday and the Manila International Conference held in his honor     

Orientations of circle graphs

Let C(v₁, …,v_n) be a system consisting of a circle C with chords v₁, …,v_n on it having different endpoints. Define a graph G having vertex set V(G) = {v₁, …,v_n} and for which vertices v_i and v_j are adjacent in G if the chords v_i and v_j intersect. Such a graph will be called a circle graph. The chords divide the interior of C into a number of regions. We give a method which associates to each such region an orientation of the edges of G. For a given C(v₁, …,v_n) the number m of different orientations corresponding to it satisfies q + 1 ≤ m ≤ n + q + 1, where q is the number of edges in G. An oriented graph obtained from a diagram C(v₁, …,v_n) as above is called an oriented circle graph (OCG). We show that transitive orientations of permutation graphs are OCGs, and give a characterization of tournaments which are OCGs. When the region is a peripheral one, the orientation of G is acyclic. In this case we define a special orientation of the complement of G, and use this to develop an improved algorithm for finding a maximum independent set in G.     

On the Wiener Index of Graphs

The Wiener index of a graph G is defined as W(G)=∑ _u,v d _G (u,v), where d _G (u,v) is the distance between u and v in G and the sum goes over all the pairs of vertices. In this paper, we first present the 6 graphs with the first to the sixth smallest Wiener index among all graphs with n vertices and k cut edges and containing a complete subgraph of order n−k; and then we construct a graph with its Wiener index no less than some integer among all graphs with n vertices and k cut edges.     

Even graphs

A nontrivial connected graph G is called even if for each vertex v of G there is a unique vertex v such that d(v, v ) = diam G. Special classes of even graphs are defined and compared to each other. In particular, an even graph G is called symmetric if d(u, v) + d(u, v ) = diam G for all u, v ∈ V(G). Several properties of even and symmetric even graphs are stated. For an even graph of order n and diameter d other than an even cycle it is shown that n ≥ 3d – 1 and conjectured that n ≥ 4d – 4. This conjecture is proved for symmetric even graphs and it is shown that for each pair of integers n, d with n even, d ≥ 2 and n ≥ 4d – 4 there exists an even graph of order n and diameter d. Several ways of constructing new even graphs from known ones are presented.     

Hamiltonian Cycles in Almost Claw-Free Graphs

 Some known results on claw-free graphs are generalized to the larger class of almost claw-free graphs. In this paper, we prove the following two results and conjecture that every 5-connected almost claw-free graph is hamiltonian. (1). Every 2-connected almost claw-free graph G∉J on n≤ 4 δ vertices is hamiltonian, where J is the set of all graphs defined as follows: any graph G in J can be decomposed into three disjoint connected subgraphs G ₁, G ₂ and G ₃ such that E _G (G _i , G _j ) = {u _i , u _j , v _i v _j } for i≠j and i,j = 1, 2, 3 (where u _i ≠v _i ∈V(G _i ) for i = 1, 2, 3). Moreover the bound 4δ is best possible, thereby fully generalizing several previous results. (2). Every 3-connected almost claw-free graph on at most 5δ−5 vertices is hamiltonian, hereby fully generalizing the corresponding result on claw-free graphs. Received: September 21, 1998 Final version received: August 18, 1999     

Independent Sets in Graph Powers are Almost Contained in Juntas

Let G = (V,E) be a simple undirected graph. Define G ⁿ , the n-th power of G, as the graph on the vertex set V ⁿ in which two vertices (u ₁, . . . , u _n ) and (v ₁, . . . , v _n ) are adjacent if and only if u _i is adjacent to v _i in G for every i. We give a characterization of all independent sets in such graphs whenever G is connected and non-bipartite. Consider the stationary measure of the simple random walk on G ⁿ . We show that every independent set is almost contained with respect to this measure in a junta, a cylinder of constant co-dimension. Moreover we show that the projection of that junta defines a nearly independent set, i.e. it spans few edges (this also guarantees that it is not trivially the entire vertex-set). Our approach is based on an analog of Fourier analysis for product spaces combined with spectral techniques and on a powerful invariance principle presented in [MoOO]. This principle has already been shown in [DiMR] to imply that independent sets in such graph products have an influential coordinate. In this work we prove that in fact there is a set of few coordinates and a junta on them that capture the independent set almost completely. I.D. is the incumbent of the Harry and Abe Sherman Lectureship Chair at Hebrew Univeristy. Her research is supported by the Israel Science Foundation and by the Binational Science Foundation. E.F.’s research is supported in part by the Israel Science Foundation, grant no. 0329745. O.R. is supported by an Alon Fellowship, by the Binational Science Foundation, by the Israel Science Foundation, and by the European Commission under the Integrated Project QAP funded by the IST directorate as Contract Number 015848.     

Decompositions of complete graphs and complete bipartite graphs into isomorphic supersubdivision graphs

A graph H is called a supersubdivison of a graph G if H is obtained from G by replacing every edge uv of G by a complete bipartite graph K_2,m (m may vary for each edge) by identifying u and v with the two vertices in K_2,m that form one of the two partite sets. We denote the set of all such supersubdivision graphs by SS(G). Then, we prove the following results.

1. Each non-trivial connected graph G and each supersubdivision graph HSS(G) admits an α-valuation. Consequently, due to the results of Rosa (in: Theory of Graphs, International Symposium, Rome, July 1966, Gordon and Breach, New York, Dunod, Paris, 1967, p. 349) and El-Zanati and Vanden Eynden (J. Combin. Designs 4 (1996) 51), it follows that complete graphs K_2cq+1 and complete bipartite graphs K_mq,nq can be decomposed into edge disjoined copies of HSS(G), for all positive integers m,n and c, where q=|E(H)|.

2. Each connected graph G and each supersubdivision graph in SS(G) is strongly n-elegant, where n=|V(G)| and felicitous.

3. Each supersubdivision graph in EASS(G), the set of all even arbitrary supersubdivision graphs of any graph G, is cordial.

Further, we discuss a related open problem.     

Lollipop graphs are extremal for commute times

Consider a simple random walk on a connected graph G=(V, E). Let C(u, v) be the expected time taken for the walk starting at vertex u to reach vertex v and then go back to u again, i.e., the commute time for u and v, and let C(G)=max_{u, v∈V}C(u, v). Further, let 𝒢(n, m) be the family of connected graphs on n vertices with m edges, , and let 𝒢(n)=∪_m𝒢(n, m) be the family of all connected n‐vertex graphs. It is proved that if G∈(n, m) is such that C(G)=max_{H∈𝒢(n, m)}C(H) then G is either a lollipop graph or a so‐called double‐handled lollipop graph. It is further shown, using this result, that if C(G)=max_H∈𝒢(n)C(H) then G is the full lollipop graph or a full double‐handled lollipop graph with [(2n−1)/3] vertices in the clique unless n≤9 in which case G is the n‐path. ©2000 John Wiley & Sons, Inc. Random Struct. Alg., 16, 131–142, 2000     

A Magnetic Procedure for the Stability Number

A magnet is a pair u, v of adjacent vertices such that the proper neighbours of u are completely linked to the proper neighbours of v. It has been shown that one can reduce the graph by removing the two vertices u, v of a magnet and introducing a new vertex linked to all common neighbours of u and v without changing the stability number. We prove that all graphs containing no chordless cycle C _k (k ≥ 5) and none of eleven forbidden subgraphs can be reduced to a stable set by repeated use of magnets. For such graphs a polynomial algorithm is given to determine the stability number.     

On the rank spread of graphs

For a simple graph G?=?(𝒱, ?) with vertex-set 𝒱?=?{1,?…?,?n}, let 𝒮(G) be the set of all real symmetric n-by-n matrices whose graph is G. We present terminology linking established as well as new results related to the minimum rank problem, with spectral properties in graph theory. The minimum rank mr(G) of G is the smallest possible rank over all matrices in 𝒮(G). The rank spread r _v (G) of G at a vertex v, defined as mr(G)???mr(G???v), can take values ??∈?{0,?1,?2}. In general, distinct vertices in a graph may assume any of the three values. For ??=?0 or 1, there exist graphs with uniform r _v (G) (equal to the same integer at each vertex v). We show that only for ??=?0, will a single matrix A in 𝒮(G) determine when a graph has uniform rank spread. Moreover, a graph G, with vertices of rank spread zero or one only, is a λ-core graph for a λ-optimal matrix A in 𝒮(G). We also develop sufficient conditions for a vertex of rank spread zero or two and a necessary condition for a vertex of rank spread two.     

Geodesic-pancyclic graphs

A shortest path connecting two vertices u and v is called a u-v geodesic. The distance between u and v in a graph G, denoted by d_G(u,v), is the number of edges in a u-v geodesic. A graph G with n vertices is panconnected if, for each pair of vertices u,v∈V(G) and for each integer k with d_G(u,v)?k?n-1, there is a path of length k in G that connects u and v. A graph G with n vertices is geodesic-pancyclic if, for each pair of vertices u,v∈V(G), every u-v geodesic lies on every cycle of length k satisfying max{2d_G(u,v),3}?k?n. In this paper, we study sufficient conditions of geodesic-pancyclic graphs. In particular, we show that most of the known sufficient conditions of panconnected graphs can be applied to geodesic-pancyclic graphs.     

Hamiltonicity of 3-Arc Graphs

An arc of a graph is an oriented edge and a 3-arc is a 4-tuple (v, u, x, y) of vertices such that both (v, u, x) and (u, x, y) are paths of length two. The 3-arc graph of a graph G is defined to have vertices the arcs of G such that two arcs uv, xy are adjacent if and only if (v, u, x, y) is a 3-arc of G. We prove that any connected 3-arc graph is hamiltonian, and all iterative 3-arc graphs of any connected graph of minimum degree at least three are hamiltonian. As a corollary we obtain that any vertex-transitive graph which is isomorphic to the 3-arc graph of a connected arc-transitive graph of degree at least three must be hamiltonian. This confirms the conjecture, for this family of vertex-transitive graphs, that all vertex-transitive graphs with finitely many exceptions are hamiltonian. We also prove that if a graph with at least four vertices is Hamilton-connected, then so are its iterative 3-arc graphs.     

On the complexity of reconstructing H‐free graphs from their Star Systems

In the Star System problem we are given a set system and asked whether it is realizable by the multi‐set of closed neighborhoods of some graph, i.e. given subsets S₁, S₂, …, S_n of an n‐element set V does there exist a graph G = (V, E) with {N[v]: v∈V} = {S₁, S₂, …, S_n}? For a fixed graph H the H‐free Star System problem is a variant of the Star System problem where it is asked whether a given set system is realizable by closed neighborhoods of a graph containing no H as an induced subgraph. We study the computational complexity of the H‐free Star System problem. We prove that when H is a path or a cycle on at most four vertices the problem is polynomial time solvable. In complement to this result, we show that if H belongs to a certain large class of graphs the H‐free Star System problem is NP‐complete. In particular, the problem is NP‐complete when H is either a cycle or a path on at least five vertices. This yields a complete dichotomy for paths and cycles. Copyright © 2010 John Wiley & Sons, Ltd. 68:113‐124, 2011     

Almost 2-Homogeneous Graphs and Completely Regular Quadrangles

Many known distance-regular graphs have extra combinatorial regularities: One of them is t-homogeneity. A bipartite or almost bipartite distance-regular graph is 2-homogeneous if the number γ _i  = |{x | ∂(u, x) = ∂(v, x) = 1 and ∂(w, x) = i − 1}| (i = 2, 3,..., d) depends only on i whenever ∂(u, v) = 2 and ∂(u, w) = ∂(v, w) = i. K. Nomura gave a complete classification of bipartite and almost bipartite 2-homogeneous distance-regular graphs. In this paper, we generalize Nomura’s results by classifying 2-homogeneous triangle-free distance-regular graphs. As an application, we show that if Γ is a distance-regular graph of diameter at least four such that all quadrangles are completely regular then Γ is isomorphic to a binary Hamming graph, the folded graph of a binary Hamming graph or the coset graph of the extended binary Golay code of valency 24. We also consider the case Γ is a parallelogram-free distance-regular graph. This research was partially supported by the Grant-in-Aid for Scientific Research (No.17540039), Japan Society of the Promotion of Science.     

Proof of a conjecture on connectivity of Kronecker product of graphs

For a graph G, κ(G) denotes its connectivity. The Kronecker product G₁×G₂ of graphs G₁ and G₂ is the graph with the vertex set V(G₁)×V(G₂), two vertices (u₁,v₁) and (u₂,v₂) being adjacent in G₁×G₂ if and only if u₁u₂∈E(G₁) and v₁v₂∈E(G₂). Guji and Vumar [R. Guji, E. Vumar, A note on the connectivity of Kronecker products of graphs, Appl. Math. Lett. 22 (2009) 1360–1363] conjectured that for any nontrivial graph G, κ(G×K_n)=min{nκ(G),(n−1)δ(G)} when n≥3. In this note, we confirm this conjecture to be true.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011