The complexity of cover graph recognition for some varieties of finite lattices

We address the following decision problem: Instance: an undirected graphG. Problem: IsG a cover graph of a lattice? We prove that this problem is NP-complete. This extends results of Brightwell [5] and Ne?et?il and Rödl [12]. On the other hand, it follows from Alvarez theorem [2] that recognizing cover graphs of modular or distributive lattices is in P. An important tool in the proof of the first result is the following statement which may be of independent interest: Given an integerl, l?3, there exists an algorithm which for a graphG withn vertices yields, in time polynomial inn, a graphH with the number of vertices polynomial inn, and satisfying girth(H)?l and χ(H)=χ(G).     

On Turán’s theorem for sparse graphs

For a graphG withn vertices and average valencyt, Turán’s theorem yields the inequalityα≧n/(t+1) whereα denotes the maximum size of an independent set inG. We improve this bound for graphs containing no large cliques.     

The eavesdropping number of a graph

Let G be a connected, undirected graph without loops and without multiple edges. For a pair of distinct vertices u and v, a minimum {u, v}-separating set is a smallest set of edges in G whose removal disconnects u and v. The edge connectivity of G, denoted λ(G), is defined to be the minimum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. We introduce and investigate the eavesdropping number, denoted ε(G), which is defined to be the maximum cardinality of a minimum {u, v}-separating set as u and v range over all pairs of distinct vertices in G. Results are presented for regular graphs and maximally locally connected graphs, as well as for a number of common families of graphs.     

Panconnected graphs II

A graphG of orderp is said to bepanconnected if for each pairu, v of vertices ofG, there exists a,u, v-path of lengthl inG, for eachl such that d_G(u, v)lp – 1, whered _G (u, v) denotes the length of a shortestu, v-path inG. Three conditions are shown to be sufficient for a graphG of orderp to be panconnected: (1) the degree of each vertex ofG is at least (p+2)/2; (2) the sum of the degrees of each pair of nonadjacent vertices ofG is at least (3p–2)/2; (3) the graphG has at least edges. It is also shown that each of these conditions is best possible. Additional results on panconnectedness are obtained including a characterization of those completen-partite graphs which are panconnected.     

Maximum Orbit Weights in the σ-game and Lit-only σ-game on Grids and Graphs

Let G be a graph in which each vertex can be in one of two states: on or off. In the σ-game, when you “push” a vertex v you change the state of all of its neighbors, while in the σ⁺-game you change the state of v as well. Given a starting configuration of on vertices, the object of both games is to reduce it, by a sequence of pushes, to the smallest possible number of on vertices. We show that any starting configuration in a graph with no isolated vertices can, by a sequence of pushes, be reduced to at most half on, and we characterize those graphs for which you cannot do better. The proofs use techniques from coding theory. In the lit-only versions of these two games, you can only push vertices which are on. We obtain some results on the minimum number of on vertices one can obtain in grid graphs in the regular and lit-only versions of both games.     

Sum List Coloring Graphs

Let G=(V,E) be a graph with n vertices and e edges. The sum choice number of G is the smallest integer p such that there exist list sizes (f(v):v ∈ V) whose sum is p for which G has a proper coloring no matter which color lists of size f(v) are assigned to the vertices v. The sum choice number is bounded above by n+e. If the sum choice number of G equals n+e, then G is sum choice greedy. Complete graphs K_n are sum choice greedy as are trees. Based on a simple, but powerful, lemma we show that a graph each of whose blocks is sum choice greedy is also sum choice greedy. We also determine the sum choice number of K_2,n, and we show that every tree on n vertices can be obtained from K_n by consecutively deleting single edges where all intermediate graphs are sc-greedy.     

Opposition graphs are strict quasi-parity graphs

An opposition graph is a graph whose edges can be acyclically oriented in such a way that every chordless path on four vertices has its extreme edges both pointing in or pointing out. A strict quasi-parity graph is a graphG such that every induced subgraphH ofG either is a clique or else contains a pair of vertices which are not endpoints of an odd (number of edges) chordless path ofH. The perfection of opposition graphs and strict quasi-parity graphs was established respectively by Olariu and Meyniel. We show here that opposition graphs are strict quasi-parity graphs.The second author acknowledges the support of the Air Force Office of Scientific Research under grant number AFOSR 0271 to Rutgers University.     

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     

Transversal hypergraphs to perfect matchings in bipartite graphs: Characterization and generation algorithms

A minimal blocker in a bipartite graph G is a minimal set of edges the removal of which leaves no perfect matching in G. We give an explicit characterization of the minimal blockers of a bipartite graph G. This result allows us to obtain a polynomial delay algorithm for finding all minimal blockers of a given bipartite graph. Equivalently, we obtain a polynomial delay algorithm for listing the anti‐vertices of the perfect matching polytope of G. We also provide generation algorithms for other related problems, including d‐factors in bipartite graphs, and perfect 2‐matchings in general graphs. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 209–232, 2006     

Removable edges in cyclically 4-edge-connected cubic graphs

We consider various ways of obtaining smaller cyclically 4-edge-connected cubic graphs from a given such graph. In particular, we consider removable edges: an edgee of a cyclically 4-edge-connected cubic graphG is said to be removable ifG is also cyclically 4-edge-connected, whereG is the cubic graph obtained fromG by deletinge and suppressing the two vertices of degree 2 created by the deletion. We prove that any cyclically 4-edge-connected cubic graphG with at least 12 vertices has at least 1/5(|E(G)| + 12) removable edges, and we characterize the graphs with exactly 1/5(|E(G)| + 12) removable edges.This work was carried out while the first author held a Niels Bohr Fellowship from the Royal Danish Academy of Sciences.