Absolute retracts of bipartite graphs

A bipartite graph G is an absolute retract if every isometric embedding g of G into a bipartite graph H is a coretraction (that is, there exists an edge-preserving map h from H to G such that hg is the identity map on G). Examples of absolute retracts are provided by chordal bipartite graphs and the covering graphs of modular lattices of breadth two. We give a construction and several characterizations of bipartite absolute retracts involving Helly type conditions. Bipartite absolute retracts apply to competitive location theory: they are precisely those bipartite graphs on which locational equilibria (Condorcet solutions) always exist.All graphs in this paper are finite, connected, and without loops or multiple edges.     

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.     

Finite common coverings of pairs of regular graphs

The graph G is a covering of the graph H if there exists a (projection) map p from the vertex set of G to the vertex set of H which induces a one-to-one correspondence between the vertices adjacent to v in G and the vertices adjacent to p(v) in H, for every vertex v of G. We show that for any two finite regular graphs G and H of the same degree, there exists a finite graph K that is simultaneously a covering both of G and H. The proof uses only Hall's theorem on 1-factors in regular bipartite graphs.     

Separating quasiconvex subgroups of right-angled Artin groups

A graph group, or right-angled Artin group, is a group given by a presentation where the only relators are commutators of the generators. A graph group presentation corresponds in a natural way to a simplicial graph, with each generator corresponding to a vertex, and each commutator relator corresponding to an edge. Suppose that G is a graph group whose corresponding graph is a tree and H is a subgroup of G. We show that if H is quasiconvex with respect to either the word metric on G or the CAT(0) metric on the universal cover of the standard complex for G, then H is separable, that is, H is the intersection of finite index subgroups of G. We also discuss some consequences relating to certain 3-manifold groups. Received: 19 July 2000; in final form: 2 March 2001 / Published online: 29 April 2002     

On the parity of planar covers

A covering is a graph map ?: G → H that is an isomorphism when restricted to the star of any vertex of G. If H is connected then |?^?1(v)| is constant. This constant is called the fold number. In this paper we prove that if G is a planar graph that covers a nonplanar H, then the fold number must be even.     

Cores of Imprimitive Symmetric Graphs of Order a Product of Two Distinct Primes

A retract of a graph Γ is an induced subgraph Ψ of Γ such that there exists a homomorphism from Γ to Ψ whose restriction to Ψ is the identity map. A graph is a core if it has no nontrivial retracts. In general, the minimal retracts of a graph are cores and are unique up to isomorphism; they are called the core of the graph. A graph Γ is G‐symmetric if G is a subgroup of the automorphism group of Γ that is transitive on the vertex set and also transitive on the set of ordered pairs of adjacent vertices. If in addition the vertex set of Γ admits a nontrivial partition that is preserved by G, then Γ is an imprimitive G‐symmetric graph. In this paper cores of imprimitive symmetric graphs Γ of order a product of two distinct primes are studied. In many cases the core of Γ is determined completely. In other cases it is proved that either Γ is a core or its core is isomorphic to one of two graphs, and conditions on when each of these possibilities occurs is given.     

On the Metric Dimension of Infinite Graphs

A set of vertices S resolves a connected graph G if every vertex is uniquely determined by its vector of distances to the vertices in S. The metric dimension of a graph G is the minimum cardinality of a resolving set. In this paper we undertake the metric dimension of infinite locally finite graphs, i.e., those infinite graphs such that all its vertices have finite degree. We give some necessary conditions for an infinite graph to have finite metric dimension and characterize infinite trees with finite metric dimension. We also establish some general results about the metric dimension of the Cartesian product of finite and infinite graphs, and obtain the metric dimension of the Cartesian product of several families of graphs.     

The Chen–Chvátal conjecture for metric spaces induced by distance-hereditary graphs

A classical theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvátal conjectured a generalization of this result to arbitrary finite metric spaces, with a particular definition of lines in a metric space. We prove it for metric spaces induced by connected distance-hereditary graphs—a graph $G$ is called distance-hereditary if the distance between two vertices $u$ and $v$ in any connected induced subgraph $H$ of $G$ is equal to the distance between $u$ and $v$ in $G$.     

Lower Bounds on the Distortion of Embedding Finite Metric Spaces in Graphs

The main question discussed in this paper is how well a finite metric space of size n can be embedded into a graph with certain topological restrictions. The existing constructions of graph spanners imply that any n -point metric space can be represented by a (weighted) graph with n vertices and n ^{1 +O(1/r)} edges, with distances distorted by at most r . We show that this tradeoff between the number of edges and the distortion cannot be improved, and that it holds in a much more general setting. The main technical lemma claims that the metric space induced by an unweighted graph H of girth g cannot be embedded in a graph G (even if it is weighted) of smaller Euler characteristic, with distortion less than g/4 - 3/2 . In the special case when |V(G)| =|V(H)| and G has strictly less edges than H , an improved bound of g/3 - 1 is shown. In addition, we discuss the case χ(G) < χ(H) - 1 , as well as some interesting higher-dimensional analogues. The proofs employ basic techniques of algebraic topology. Received September 26, 1995, and in revised form March 18, 1996.     

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     

On H-Linked Graphs

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). This notion clearly generalizes the concept of k-linked graphs (as well as other properties). In this paper we determine, for a connected multigraph H and for any sufficiently large graph G, a sharp lower bound on δ(G) (depending upon H) such that G is H-linked.     

Unique and faithful embeddings of projective-planar graphs

A graph G is uniquely embeddable in a surface F² if for any two embeddings f₁,f₂: G → F², there exists an isomorphism σ: G → G and a homeomorphism h: F² → F² for which h → f₁ = f₂ σ. A graph G is faithfully embeddable in a surface F² if G admits an embedding f: G → F² such that for any isomorphism σ: G → G, there is a homeomorphism h: F² → F² with h → f = f → σ. It will be shown that if a projective-planar graph G is 5-connected and contains a subdivision of the complete graph K₆ as its subgraph, then G is uniquely embeddable in a projective plane, and that moreover if G is not isomorphic to K₆, then G is faithfully embeddable in a projective plane.     

Connectivity of intersection graphs of finite groups

The intersection graph of a group G is an undirected graph without loops and multiple edges defined as follows: the vertex set is the set of all proper non-trivial subgroups of G, and there is an edge between two distinct vertices H and K if and only if H∩K≠1 where 1 denotes the trivial subgroup of G. In this paper, we classify finite solvable groups whose intersection graphs are not 2-connected and finite nilpotent groups whose intersection graphs are not 3-connected. Our methods are elementary.     

Noncyclic Graph of a Group

We associate a graph Γ _G to a nonlocally cyclic group G (called the noncyclic graph of G) as follows: take G\ Cyc(G) as vertex set, where Cyc(G) = {x ? G| 〈x, y〉 is cyclic for all y ? G}, and join two vertices if they do not generate a cyclic subgroup. We study the properties of this graph and we establish some graph theoretical properties (such as regularity) of this graph in terms of the group ones. We prove that the clique number of Γ _G is finite if and only if Γ _G has no infinite clique. We prove that if G is a finite nilpotent group and H is a group with Γ _G  ? Γ _H and |Cyc(G)| = |Cyc(H)| = 1, then H is a finite nilpotent group. We give some examples of groups G whose noncyclic graphs are “unique”, i.e., if Γ _G  ? Γ _H for some group H, then G ? H. In view of these examples, we conjecture that every finite nonabelian simple group has a unique noncyclic graph. Also we give some examples of finite noncyclic groups G with the property that if Γ _G  ? Γ _H for some group H, then |G| = |H|. These suggest the question whether the latter property holds for all finite noncyclic groups.     

On retracts,absolute retracts,and foldings in cographs

A retract of a graph G is an induced subgraph H of G such that there exists a homomorphism \(\rho :G \rightarrow H\). When both G and H are cographs, we show that the problem to determine whether H is a retract of G is NP-complete; moreover, we show that this problem on cographs is fixed-parameter tractable when parameterized by the size of H. When restricted to the class of threshold graphs or to the class of trivially perfect graphs, the retract problem becomes tractable in polynomial time. The retract problem is also solvable in linear time when one cograph is given as an induced subgraph of the other. We characterize absolute retracts for the class of cographs. Foldings generalize retractions. We show that the problem to fold a trivially perfect graph onto a largest possible clique is NP-complete.     

On possible counterexamples to Negami's planar cover conjecture

A simple graph H is a cover of a graph G if there exists a mapping φ from H onto G such that φ maps the neighbors of every vertex υ in H bijectively to the neighbors of φ (υ) in G . Negami conjectured in 1986 that a connected graph has a finite planar cover if and only if it embeds in the projective plane. The conjecture is still open. It follows from the results of Archdeacon, Fellows, Negami, and the first author that the conjecture holds as long as the graph K _1,2,2,2 has no finite planar cover. However, those results seem to say little about counterexamples if the conjecture was not true. We show that there are, up to obvious constructions, at most 16 possible counterexamples to Negami's conjecture. Moreover, we exhibit a finite list of sets of graphs such that the set of excluded minors for the property of having finite planar cover is one of the sets in our list. © 2004 Wiley Periodicals, Inc. J Graph Theory 46: 183–206, 2004     

Degree-bounded coloring of graphs: Variations on a theme by brooks

A graph G is degree-bounded-colorable (briefly, db-colorable) if it can be properly vertex-colored with colors 1,2, …, k ≤ Δ(G) such that each vertex v is assigned a color c(v) ≤ v. We first prove that if a connected graph G has a block which is neither a complete graph nor an odd cycle, then G is db-colorable. One may think of this as an improvement of Brooks' theorem in which the global bound Δ(G) on the number of colors is replaced by the local bound deg v on the color at vertex v. Extending the above result, we provide an algorithmic characterization of db-colorable graphs, as well as a nonalgorithmic characterization of db-colorable trees. We briefly examine the problem of determining the smallest integer k such that G is db-colorable with colors 1, 2,…, k. Finally, we extend these results to set coloring. © 1995, John Wiley & Sons, Inc.     

Odd‐angulated graphs and cancelling factors in box products

Under what conditions is it true that if there is a graph homomorphism G □ H → G □ T, then there is a graph homomorphism H→ T? Let G be a connected graph of odd girth 2k + 1. We say that G is (2k + 1)‐angulated if every two vertices of G are joined by a path each of whose edges lies on some (2k + 1)‐cycle. We call G strongly (2k + 1)‐angulated if every two vertices are connected by a sequence of (2k + 1)‐cycles with consecutive cycles sharing at least one edge. We prove that if G is strongly (2k + 1)‐angulated, H is any graph, S, T are graphs with odd girth at least 2k + 1, and ?: G□ H→S□T is a graph homomorphism, then either ? maps G□{h} to S□{t_h} for all h∈V(H) where t_h∈V(T) depends on h; or ? maps G□{h} to {s_h}□ T for all h∈V(H) where s_h∈V(S) depends on h. This theorem allows us to prove several sufficient conditions for a cancelation law of a graph homomorphism between two box products with a common factor. We conclude the article with some open questions. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:221‐238, 2008     

Bi‐arc graphs and the complexity of list homomorphisms

Given graphs G, H, and lists L(v) ? V(H), v ε V(G), a list homomorphism of G to H with respect to the lists L is a mapping f : V(G) → V(H) such that uv ε E(G) implies f(u)f(v) ε E(H), and f(v) ε L(v) for all v ε V(G). The list homomorphism problem for a fixed graph H asks whether or not an input graph G, together with lists L(v) ? V(H), v ε V(G), admits a list homomorphism with respect to L. In two earlier papers, we classified the complexity of the list homomorphism problem in two important special cases: When H is a reflexive graph (every vertex has a loop), the problem is polynomial time solvable if H is an interval graph, and is NP‐complete otherwise. When H is an irreflexive graph (no vertex has a loop), the problem is polynomial time solvable if H is bipartite and H is a circular arc graph, and is NP‐complete otherwise. In this paper, we extend these classifications to arbitrary graphs H (each vertex may or may not have a loop). We introduce a new class of graphs, called bi‐arc graphs, which contains both reflexive interval graphs (and no other reflexive graphs), and bipartite graphs with circular arc complements (and no other irreflexive graphs). We show that the problem is polynomial time solvable when H is a bi‐arc graph, and is NP‐complete otherwise. In the case when H is a tree (with loops allowed), we give a simpler algorithm based on a structural characterization. © 2002 Wiley Periodicals, Inc. J Graph Theory 42: 61–80, 2003