On Switching to H‐Free Graphs

In this article, we study the problem of deciding if, for a fixed graph H, a given graph is switching equivalent to an H‐free graph. Polynomial‐time algorithms are known for H having at most three vertices or isomorphic to P₄. We show that for H isomorphic to a claw, the problem is polynomial, too. On the other hand, we give infinitely many graphs H such that the problem is NP‐complete, thus solving an open problem [Kratochvíl, Ne?et?il and Zýka, Ann Discrete Math 51 (1992)]. Further, we give a characterization of graphs switching equivalent to a K_{1, 2}‐free graph by ten forbidden‐induced subgraphs, each having five vertices. We also give the forbidden‐induced subgraphs for graphs switching equivalent to a forest of bounded vertex degrees.     

Packing tight Hamilton cycles in 3‐uniform hypergraphs

Let H be a 3‐uniform hypergraph with n vertices. A tight Hamilton cycle C ? H is a collection of n edges for which there is an ordering of the vertices v₁,…,v_n such that every triple of consecutive vertices {v_i,v_i+1,v_i+2} is an edge of C (indices are considered modulo n ). We develop new techniques which enable us to prove that under certain natural pseudo‐random conditions, almost all edges of H can be covered by edge‐disjoint tight Hamilton cycles, for n divisible by 4. Consequently, we derive the corollary that random 3‐uniform hypergraphs can be almost completely packed with tight Hamilton cycles whp, for n divisible by 4 and p not too small. Along the way, we develop a similar result for packing Hamilton cycles in pseudo‐random digraphs with even numbers of vertices. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Orthogonal one-factorization graphs

An orthogonal one-factorization graph (OOFG) is a graph in which the vertices are one-factorizations of some underlying graph H, and two vertices are adjacent if and only if the one-factorizations are orthogonal. An arbitrary finite graph, G, is realizable if there is an OOFG isomorphic to G. We show that every finite graph is realizable as an OOFG with underlying graph K_n for some n. We also discuss some special cases.     

Implications among linkage properties in graphs

Given a graph H with vertices w₁, …, w_m, a graph G with at least m vertices is H‐linked if for every choice of vertices v₁, …, v_m in G, there is a subdivision of H in G such that v_i is the branch vertex representing w_i (for all i ). This concept generalizes the notions of k‐linked, k‐connected, and k‐ordered graphs. For graphs H₁ and H₂ with the same order that are not contained in stars, the property of being H₁‐linked implies that of being H₂‐linked if and only if H₂?H₁. The implication also holds when H₁ is obtained from H₂ by replacing an edge xy with an edge from y to a new vertex x′. Other instances of nonimplication are obtained, using a lemma that the number of vertices appearing in minimum vertex covers of a graph G is at most the vertex cover number plus the size of a maximum matching. © 2009 Wiley Periodicals, Inc. J Graph Theory 60: 327‐337, 2009     

On H‐immersions

For a fixed multigraph H, possibly containing loops, with V(H) = {h₁,…, h_k}, we say a graph G is H‐linked if for every choice of k vertices v₁,…,v_k in G, there exists a subdivision of H in G such that v_i represents h_i (for all i). An H‐immersion in G is similar except that the paths in G, playing the role of the edges of H, are only required to be edge disjoint. In this article, we extend the notion of an H‐linked graph by determining minimum degree conditions for a graph G to contain an H‐immersion with a bounded number of vertex repetitions on any choice of k vertices. In particular, we extend results found in [2,3,5]. © 2007 Wiley Periodicals, Inc. J Graph Theory 57: 245–254, 2008     

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.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Forbidden induced subgraph characterization of cograph contractions

Let S₁, S₂,…,S_t be pairwise disjoint non‐empty stable sets in a graph H. The graph H^* is obtained from H by: (i) replacing each S_i by a new vertex q_i; (ii) joining each q_i and q_j, 1 ≤ i # j ≤ t, and; (iii) joining q_i to all vertices in H – (S₁ ∪ S₂ ∪ ··· ∪ S_t) which were adjacent to some vertex of S_i. A cograph is a P₄‐free graph. A graph G is called a cograph contraction if there exist a cograph H and pairwise disjoint non‐empty stable sets in H for which G ? H^*. Solving a problem proposed by Le [ 2 ], we give a finite forbidden induced subgraph characterization of cograph contractions. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 217–226, 2004     

GEODETIC GAMES FOR GRAPHS

ABSTRACT

Let S be a subset of the vertex set V(G) of a nontrivial connected graph G. The geodetic closure (S) of S is the set of all vertices on geodesics between two vertices in S. The first player A chooses a vertex v₁ of G. The second player B then picks v₂ ≠ v₁ and forms the geodetic closure (S₂) = ({v₁, v₂}). Now A selects v₃ ε V—S₂ and forms (S₃) = ({v₁, v₂, v₃}), etc. The player who first selects a vertex v_n such that (S_n) = V wins the achievement game, but loses the avoidance game. These geodetic achievement and avoidance games are solved for several families of graphs by determining which player is the winner.     

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     

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     

Packing graphs with odd and even trees

The Gyárfás-Lehel tree-packing conjecture asserts that any sequence T₁, T₂, …, T_n^?1 of trees with 1, 2, …, n - 1 edges packs into the complete graph K_n on n vertices. The present paper examines two conjectures that jointly imply the Gyárfás-Lehel conjecture: 1. For n even, any T₁, T₃, …, T_n^?1 pack into the half-complete graph Hn on n vertices.2. For n odd, any T₂, T₄, …, T_n^?1 pack into the half-complete graph Hn on n vertices. The H_n are uniquely defined by their degree sequences: H_n and H_n+1 are complements in K_n+1. It is shown that H_n and T_n+1 pack into H_n+2 if T_n+1 is a double star, unimodal triple star, interior-3 caterpillar, or scorpion. Hence Conjectures 1 and 2 are true for these specialized types of trees. The conjectures are also valid for all trees when n ≤ 9, so that the Gyárfás-Lehel conjecture holds for n ≤ 9.     

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.     

Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement

Given a complete graph K_n=(V,E)with edge weight c_e on each edge, we consider the problem of partitioning the vertices of graph K_n into subcliques that have at least S vertices, so as to minimize the total weight of the edges that have both endpoints in the same subclique. In this paper, we consider using the branch-and-price method to solve the problem. We demonstrate the necessity of cutting planes for this problem and suggest effective ways of adding cutting planes in the branch-and-price framework. The NP hard pricing problem is solved as an integer programming problem. We present computational results on large randomly generated problems.     

Further results on the lower bounds of mean color numbers

Let G be a graph with n vertices. The mean color number of G, denoted by μ(G), is the average number of colors used in all n‐colorings of G. This paper proves that μ(G) ≥ μ(Q), where Q is any 2‐tree with n vertices and G is any graph whose vertex set has an ordering x₁,x₂,…,x_n such that x_i is contained in a K₃ of G[V_i] for i = 3,4,…,n, where V_i = {x₁,x₂,…,x_i}. This result improves two known results that μ(G) ≥ μ(O_n) where O_n is the empty graph with n vertices, and μ(G) ≥ μ(T) where T is a spanning tree of G. © 2004 Wiley Periodicals, Inc. J Graph Theory 48: 51–73, 2005     

Potentially <Emphasis Type="Italic">K</Emphasis><Subscript><Emphasis Type="Italic">m</Emphasis></Subscript> — <Emphasis Type="Italic">G</Emphasis>-graphical sequences: A survey

The set of all non-increasing nonnegative integer sequences π = (d(v ₁), d(v ₂), …, d(v _n )) is denoted by NS _n . A sequence π ∈ NS _n is said to be graphic if it is the degree sequence of a simple graph G on n vertices, and such a graph G is called a realization of π. The set of all graphic sequences in NS _n is denoted by GS _n . A graphical sequence π is potentially H-graphical if there is a realization of π containing H as a subgraph, while π is forcibly H-graphical if every realization of π contains H as a subgraph. Let K _k denote a complete graph on k vertices. Let K _m −H be the graph obtained from Km by removing the edges set E(H) of the graph H (H is a subgraph of K _m ). This paper summarizes briefly some recent results on potentially K _m −G-graphic sequences and give a useful classification for determining σ (H, n).     

Extremal results for rooted minor problems

In this article, we consider the following problem. Given four distinct vertices v₁,v₂,v₃,v₄. How many edges guarantee the existence of seven connected disjoint subgraphs X_i for i = 1,…, 7 such that X_j contains v_j for j = 1, 2, 3, 4 and for j = 1, 2, 3, 4, X_j has a neighbor to each X_k with k = 5, 6, 7. This is the so called “rooted K_{3, 4}‐minor problem.” There are only few known results on rooted minor problems, for example, [15,6]. In this article, we prove that a 4‐connected graph with n vertices and at least 5n ? 14 edges has a rooted K_3,4‐minor. In the proof we use a lemma on graphs with 9 vertices, proved by computer search. We also consider the similar problems concerning rooted K_3,3‐minor problem, and rooted K_3,2‐minor problem. More precisely, the first theorem says that if G is 3‐connected and e(G) ≥ 4|G| ? 9 then G has a rooted K_3,3‐minor, and the second theorem says that if G is 2‐connected and e(G) ≥ 13/5|G| ? 17/5 then G has a rooted K_3,2‐minor. In the second case, the extremal function for the number of edges is best possible. These results are then used in the proof of our forthcoming articles 7 , 8 . © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 191–207, 2007     

Geodesics and almost geodesic cycles in random regular graphs

A geodesic in a graph G is a shortest path between two vertices of G. For a specific function e(n) of n, we define an almost geodesic cycle C in G to be a cycle in which for every two vertices u and v in C, the distance d_G(u, v) is at least d_C(u, v)?e(n). Let ω(n) be any function tending to infinity with n. We consider a random d‐regular graph on n vertices. We show that almost all pairs of vertices belong to an almost geodesic cycle C with e(n) = log_d?1log_d?1n+ ω(n) and |C| = 2log_d?1n+ O(ω(n)). Along the way, we obtain results on near‐geodesic paths. We also give the limiting distribution of the number of geodesics between two random vertices in this random graph. Copyright © 2010 John Wiley & Sons, Ltd. J Graph Theory 66:115‐136, 2011     

Diagonal norm hermitian matrices

If v is a norm on $\text{C}$ⁿ, let H(v) denote the set of all norm-Hermitians in $\text{C}$ⁿⁿ. Let S be a subset of the set of real diagonal matrices D. Then there exists a norm v such that S=H(v) (or S = H(v)∩D) if and only if S contains the identity and S is a subspace of D with a basis consisting of rational vectors. As a corollary, it is shown that, for a diagonable matrix h with distinct eigenvalues λ₁,…, λ_r, r?n, there is a norm v such that h ∈ H(v), but h^s?H(v), for some integer s, if and only if λ₂–λ₁,…, λ_r–λ₁ are linearly dependent over the rationals. It is also shown that the set of all norms v, for which H(v) consists of all real multiples of the identity, is an open, dense subset, in a natural metric, of the set of all norms.