The stable set problem and the lift-and-project ranks of graphs

We study the lift-and-project procedures for solving combinatorial optimization problems, as described by Lovász and Schrijver, in the context of the stable set problem on graphs. We investigate how the procedures' performances change as we apply fundamental graph operations. We show that the odd subdivision of an edge and the subdivision of a star operations (as well as their common generalization, the stretching of a vertex operation) cannot decrease the N₀-, N-, or N₊-rank of the graph. We also provide graph classes (which contain the complete graphs) where these operations do not increase the N₀- or the N-rank. Hence we obtain the ranks for these graphs, and we also present some graph-minor like characterizations for them. Despite these properties we give examples showing that in general most of these operations can increase these ranks. Finally, we provide improved bounds for N₊-ranks of graphs in terms of the number of nodes in the graph and prove that the subdivision of an edge or cloning a vertex can increase the N₊-rank of a graph.Research of these authors was supported in part by a PREA from Ontario, Canada and research grants from NSERC.Mathematics Subject Classification (2000): 0C10, 90C22, 90C27, 47D20     

Non-cover generalized Mycielski, Kneser, and Schrijver graphs

A graph is said to be a cover graph if it is the underlying graph of the Hasse diagram of a finite partially ordered set. We prove that the generalized Mycielski graphs M_m(C_2t+1) of an odd cycle, Kneser graphs KG(n,k), and Schrijver graphs SG(n,k) are not cover graphs when m?0,t?1, k?1, and n?2k+2. These results have consequences in circular chromatic number.     

Lift and project relaxations for the matching and related polytopes

We compare lift and project methods given by Lovász and Schrijver (the N₊ and N procedures) and by Balas, Ceria and Cornuéjols (the disjunctive procedure) when working on the matching, perfect matching and covering polytopes. When the underlying graph is the complete graph of n=2s+1 nodes we obtain that the disjunctive index for all problems is s², the N₊-index for the matching and perfect matching problems is s (extending a result by Stephen and Tunçel), the N-index for the perfect matching problem is s, and the N₊ and N indices for the covering problem and the N-index for the matching problem are strictly greater than s.     

Colourings of graphs with two consecutive odd cycle lengths

In 1992 Gyárfás showed that a graph G having only k odd cycle lengths is (2k+1)-colourable, if it does not contain a K_2k+2. In this paper, we will present the results for graphs containing only odd cycles of length 2m−1 and 2m+1 as done in [S. Matos Camacho, Colourings of graph with prescribed cycle lengths, diploma thesis, TU Bergakademie Freiberg, 2006. [3]]. We will show that these graphs are 4-colourable.     

On infinite graphs with a specified number of colorings

In this paper we construct a planar graph of degree four which admits exactly N_u 3-colorings, we prove that such a graph must have degree at least four, and we consider various generalizations. We first allow our graph to have either one or two vertices of infinite degree and/or to admit only finitely many colorings and we note how this effects the degrees of the remaining vertices. We next consider n-colorings for n>3, and we construct graphs which we conjecture (but cannot prove) are of minimal degree. Finally, we consider nondenumerable graphs, and for every 3 <n<ω and every infinite cardinal k we construct a graph of cardinality k which admits exactly kn-colorings. We also show that the number of n-colorings of a denumerable graph can never be strictly between N_u and 2^N_u and that an appropriate generalization holds for at least certain nondenumerable graphs.     

Connectivity of graphs with given girth pair

Girth pairs were introduced by Harary and Kovács [Regular graphs with given girth pair, J. Graph Theory 7 (1983) 209-218]. The odd girth (even girth) of a graph is the length of a shortest odd (even) cycle. Let g denote the smaller of the odd and even girths, and let h denote the larger. Then (g,h) is called the girth pair of the graph. In this paper we prove that a graph with girth pair (g,h) such that g is odd and h?g+3 is even has high (vertex-)connectivity if its diameter is at most h-3. The edge version of all results is also studied.     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

On linear differential Φ<Subscript>+</Subscript>-operators of elliptic type in Sobolev-Stepanov spaces

We show that a linear differential operator of elliptic type is a Φ₊-operator in the Stepanov space if and only if it is a Φ₊-operator in the Sobolev space.     

Terminable and interminable paths and trails in infinite graphs

The paper is concerned with certain kinds of random processes in infinite graphs. A finite trail of a graph which cannot be continued from either end is called terminated, and a finite trail is called terminable of it is a segment of a finite terminated trail; analogously for 1 - ∞ trails, finite paths, and 1 - ∞ paths.For k = 1,2,3,…, there exist graphs which contain 2 - ∞ paths and have node-connectivity k and in which no finite path and no 1 - ∞ path is terminable, and also such graphs in which every finite path and every 1 - ∞ path is terminable. In any graph with infinite node-connectivity every node of valency N₀ is the end-node of terminated 1 - ∞ paths. There exist graphs with node-connectivity N₀ in which every 1 - ∞ path is terminable. For λ = 1,2,3,…, there exist graphs which contain 2 - ∞ paths and have edge-connectivity λ and in which no finite trail and no 1 - ∞ trail is terminable, and also such graphs in which every finite trail and every 1 - ∞ trail is terminable. In contrast to the situation for 1 - ∞ paths, every connected infinite graph in which every 1 - ∞ trail is terminable contains at least one node of odd edge-degree and if in addition every finite trail is terminable, then there are at least two nodes of odd edge-degree.     

Small subgraphs in random graphs and the power of multiple choices

The standard paradigm for online power of two choices problems in random graphs is the Achlioptas process. Here we consider the following natural generalization: Starting with G₀ as the empty graph on n vertices, in every step a set of r edges is drawn uniformly at random from all edges that have not been drawn in previous steps. From these, one edge has to be selected, and the remaining r−1 edges are discarded. Thus after N steps, we have seen rN edges, and selected exactly N out of these to create a graph GN.In a recent paper by Krivelevich, Loh, and Sudakov (2009) [11], the problem of avoiding a copy of some fixed graph F in GN for as long as possible is considered, and a threshold result is derived for some special cases. Moreover, the authors conjecture a general threshold formula for arbitrary graphs F. In this work we disprove this conjecture and give the complete solution of the problem by deriving explicit threshold functions N₀(F,r,n) for arbitrary graphs F and any fixed integer r. That is, we propose an edge selection strategy that a.a.s. (asymptotically almost surely, i.e. with probability 1−o(1) as n→∞) avoids creating a copy of F for as long as N=o(N₀), and prove that any online strategy will a.a.s. create such a copy once N=ω(N₀).     

Strongly regular graphs associated with ternary bent functions

We prove a new characterization of weakly regular ternary bent functions via partial difference sets. Partial difference sets are combinatorial objects corresponding to strongly regular graphs. Using known families of bent functions, we obtain in this way new families of strongly regular graphs, some of which were previously unknown. One of the families includes an example in [N. Hamada, T. Helleseth, A characterization of some {3v₂+v₃,3v₁+v₂,3,3}-minihypers and some [15,4,9;3]-codes with B₂=0, J. Statist. Plann. Inference 56 (1996) 129-146], which was considered to be sporadic; using our results, this strongly regular graph is now a member of an infinite family. Moreover, this paper contains a new proof that the Coulter-Matthews and ternary quadratic bent functions are weakly regular.     

Paths, trees and matchings under disjunctive constraints

We study the minimum spanning tree problem, the maximum matching problem and the shortest path problem subject to binary disjunctive constraints: A negative disjunctive constraint states that a certain pair of edges cannot be contained simultaneously in a feasible solution. It is convenient to represent these negative disjunctive constraints in terms of a so-called conflict graph whose vertices correspond to the edges of the underlying graph, and whose edges encode the constraints.We prove that the minimum spanning tree problem is strongly NP-hard, even if every connected component of the conflict graph is a path of length two. On the positive side, this problem is polynomially solvable if every connected component is a single edge (that is, a path of length one). The maximum matching problem is NP-hard for conflict graphs where every connected component is a single edge.Furthermore we will also investigate these graph problems under positive disjunctive constraints: In this setting for certain pairs of edges, a feasible solution must contain at least one edge from every pair. We establish a number of complexity results for these variants including APX-hardness for the shortest path problem.     

Commutativity of the adjacency matrices of graphs

We say that two graphs G₁ and G₂ with the same vertex set commute if their adjacency matrices commute. In this paper, we find all integers n such that the complete bipartite graph K_n,n is decomposable into commuting perfect matchings or commuting Hamilton cycles. We show that there are at most n−1 linearly independent commuting adjacency matrices of size n; and if this bound occurs, then there exists a Hadamard matrix of order n. Finally, we determine the centralizers of some families of graphs.     

A fast parallel algorithm for finding Hamiltonian cycles in dense graphs

Suppose that 0<η<1 is given. We call a graph, G, on n vertices an η-Chvátal graph if its degree sequence d₁≤d₂≤?≤d_n satisfies: for k<n/2, d_k≤min{k+ηn,n/2} implies d_n−k−ηn≥n−k. (Thus for η=0 we get the well-known Chvátal graphs.) An -algorithm is presented which accepts as input an η-Chvátal graph and produces a Hamiltonian cycle in G as an output. This is a significant improvement on the previous best -algorithm for the problem, which finds a Hamiltonian cycle only in Dirac graphs (δ(G)≥n/2 where δ(G) is the minimum degree in G).     

Removable edges in a 5-connected graph and a construction method of 5-connected graphs

An edge e of a k-connected graph G is said to be a removable edge if G?e is still k-connected. A k-connected graph G is said to be a quasi (k+1)-connected if G has no nontrivial k-separator. The existence of removable edges of 3-connected and 4-connected graphs and some properties of quasi k-connected graphs have been investigated [D.A. Holton, B. Jackson, A. Saito, N.C. Wormale, Removable edges in 3-connected graphs, J. Graph Theory 14(4) (1990) 465-473; H. Jiang, J. Su, Minimum degree of minimally quasi (k+1)-connected graphs, J. Math. Study 35 (2002) 187-193; T. Politof, A. Satyanarayana, Minors of quasi 4-connected graphs, Discrete Math. 126 (1994) 245-256; T. Politof, A. Satyanarayana, The structure of quasi 4-connected graphs, Discrete Math. 161 (1996) 217-228; J. Su, The number of removable edges in 3-connected graphs, J. Combin. Theory Ser. B 75(1) (1999) 74-87; J. Yin, Removable edges and constructions of 4-connected graphs, J. Systems Sci. Math. Sci. 19(4) (1999) 434-438]. In this paper, we first investigate the relation between quasi connectivity and removable edges. Based on the relation, the existence of removable edges in k-connected graphs (k?5) is investigated. It is proved that a 5-connected graph has no removable edge if and only if it is isomorphic to K₆. For a k-connected graph G such that end vertices of any edge of G have at most k-3 common adjacent vertices, it is also proved that G has a removable edge. Consequently, a recursive construction method of 5-connected graphs is established, that is, any 5-connected graph can be obtained from K₆ by a number of θ⁺-operations. We conjecture that, if k is even, a k-connected graph G without removable edge is isomorphic to either K_k+1 or the graph H_k/2+1 obtained from K_k+2 by removing k/2+1 disjoint edges, and, if k is odd, G is isomorphic to K_k+1.     

Diamond-free circle graphs are Helly circle

The diamond is the graph obtained from K₄ by deleting an edge. Circle graphs are the intersection graphs of chords in a circle. Such a circle model has the Helly property if every three pairwise intersecting chords intersect in a single point, and a graph is Helly circle if it has a circle model with the Helly property. We show that the Helly circle graphs are the diamond-free circle graphs, as conjectured by Durán. This characterization gives an efficient recognition algorithm for Helly circle graphs.     

Dual graph homomorphism functions

For any two graphs F and G, let hom(F,G) denote the number of homomorphisms F→G, that is, adjacency preserving maps V(F)→V(G) (graphs may have loops but no multiple edges). We characterize graph parameters f for which there exists a graph F such that f(G)=hom(F,G) for each graph G.The result may be considered as a certain dual of a characterization of graph parameters of the form hom(.,H), given by Freedman, Lovász and Schrijver [M. Freedman, L. Lovász, A. Schrijver, Reflection positivity, rank connectivity, and homomorphisms of graphs, J. Amer. Math. Soc. 20 (2007) 37-51]. The conditions amount to the multiplicativity of f and to the positive semidefiniteness of certain matrices N(f,k).