Isometric cycles,cutsets, and crowning of bridged graphs

A graph G is bridged if every cycle C of length at least 4 has vertices x,y such that d_G(x,y) < d_C(x,y). A cycle C is isometric if d_G(x,y) = d_C(x,y) for all x,y ∈ V(C). We show that every graph contractible to a graph with girth g has an isometric cycle of length at least g. We use this to show that every minimal cutset S in a bridged graph G induces a connected subgraph. We introduce a “crowning” construction to enlarge bridged graphs. We use this to construct examples showing that for every connected simple graph H with girth at least 6 (including trees), there exists a bridged graph G such that G has a unique minimum cutset S and that G[S] = H. This provides counterexamples to Hahn's conjecture that d_G(u,v) ≤ 2 when u and v lie in a minimum cutset in a bridged graph G. We also study the convexity of cutsets in bridged graphs. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 161–170, 2003     

Dictators on blocks: Generalizations of social choice impossibility theorems

This paper extends impossibility theorems of Arrow and others to cases in which social comparisons between alternatives in a set X of social alternatives may be made only for each pair {x, y} in a certain subset of distinct pairs taken from X. With E the set of pairs within which social comparisons may be made, G = (X, E) is an undirected graph without loops. The social comparison between x and y for {x, y} ∈ E is to be based on the preferences of individuals in a finite society S. Each individual is presumed to prefer x to y or prefer y to x (not both) for every {x, y} ∈ E and may hold any preference relation that does not cycle in G. A profile is an assignment of one such relation to each individual in S. The paper examines binary social comparison procedures which map each profile into a social preference relation over the pairs in E, subject to x socially preferred to y whenever {x, y} ∈ E and everyone in S prefers x to y. Individual i ∈ S is a dictator [weak dictator] on {x, y} ∈ E iff x is socially preferred to y [x ranks as high as y socially] whenever i prefers x to y, and similarly with x and y interchanged, regardless of the preferences of the other individuals in S. An individual is a dictator [weak dictator] on a subgraph of G iff he is a dictator [weak dictator] on every edge in the subgraph. Under each of three ordering conditions on social preferences, there is a dictator or weak dictator on every block of G which has three or more points, different blocks can have different dictators, and bridges in E need not have dictators.     

On constructible graphs,locally Helly graphs,and convexity

A (finite or infinite) graph G is constructible if there exists a well‐ordering ≤ of its vertices such that for every vertex x which is not the smallest element, there is a vertex y < x which is adjacent to x and to every neighbor z of x with z < x. Particular constructible graphs are Helly graphs and connected bridged graphs. In this paper we study a new class of constructible graphs, the class of locally Helly graphs. A graph G is locally Helly if, for every pair (x,y) of vertices of G whose distance is d ≥ 2, there exists a vertex whose distance to x is d ? 1 and which is adjacent to y and to all neighbors of y whose distance to x is at most d. Helly graphs are locally Helly, and the converse holds for finite graphs. Among different properties we prove that a locally Helly graph is strongly dismantable, hence cop‐win, if and only if it contains no isometric rays. We show that a locally Helly graph G is finitely Helly, that is, every finite family of pairwise non‐disjoint balls of G has a non‐empty intersection. We give a sufficient condition by forbidden subgraphs so that the three concepts of Helly graphs, of locally Helly graphs and of finitely Helly graphs are equivalent. Finally, generalizing different results, in particular those of Bandelt and Chepoi 1 about Helly graphs and bridged graphs, we prove that the Helly number h(G) of the geodesic convexity in a constructible graph G is equal to its clique number ω(G), provided that ω(G) is finite. © 2003 Wiley Periodicals, Inc. J Graph Theory 43: 280–298, 2003     

A Mengerian theorem for paths of length at least three

Let be x, y two vertices of a graph G, such that t openly disjoint xy-paths of length ≥3 exist. In this article we show that then there exists a set S of cardinality less than or equal to 3t – 2, resp. 2t for t ∈ {1, 2, 3}, which destroys all xy-paths of length ≥3. Also a lower bound for the cardinality of S is given by constructing special graphs.     

On the Genus of the Nilpotent Graphs of Finite Groups

The nilpotent graph of a group G is a simple graph whose vertex set is G?nil(G), where nil(G) = {y ∈ G | ? x, y ? is nilpotent ? x ∈ G}, and two distinct vertices x and y are adjacent if ? x, y ? is nilpotent. In this article, we show that the collection of finite non-nilpotent groups whose nilpotent graphs have the same genus is finite, derive explicit formulas for the genus of the nilpotent graphs of some well-known classes of finite non-nilpotent groups, and determine all finite non-nilpotent groups whose nilpotent graphs are planar or toroidal.     

Proportional graphs

Let S be a finite set of graphs and t a real number, 0 < t < 1. A (deterministic) graph G is (t, 5)-proportional if for every H ∈ S, the number of induced subgraphs of G isomorphic to H equals the expected number of induced copies of H in the random graph G_{n, t} where n = |V(G)|. Let S_k = {all graphs on k vertices}, in particular S₃ = {K₃, P₂, K₂K_t, D₃}. The notion of proportional graphs stems from the study of random graphs (Barbour, Karoński, and Ruciński, J Combinat. Th. Ser. B, 47 , 125-145, 1989; Janson and Nowicki, Prob. Th. Rel. Fields, to appear, Janson, Random Struct. Alg., 1 , 15-37, 1990) where it is shown that (t, S₃)-proportional graphs play a very special role; we thus call them simply t-proportional. However, only a few ½-proportional graphs on 8 vertices were known and it was an open problem whether there are any f-proportional graphs with t ≠ ½ at all. In this paper, we show that there are infinitely many ½-proportional graphs and that there are t-proportional graphs with t≠. Both results are proved constructively. [We are not able to provide the latter construction for all f∈ Q∩(0,1), but the set of ts for which our construction works is dense in (0,1).] To support a conviction that the existence of (t, S₃)-proportional graphs was not quite obvious, we show that there are no (t, S₄)-proportional graphs.     

On clique-critical graphs

A graph G is clique-critical if G and G?x have different clique-graphs for all vertices x of G. For any graph H, there is at most a finite number of different clique-critical graphs G such that H is the clique-graph of G. Upper and lower bounds for the number of vertices of the cliques of the critical graphs are obtained.     

Diameter and connectivity 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 given graph G, X(G), is defined to have vertices the arcs of G. Two arcs uv,xy are adjacent in X(G) if and only if (v,u,x,y) is a 3-arc of G. This notion was introduced in recent studies of arc-transitive graphs. In this paper we study diameter and connectivity of 3-arc graphs. In particular, we obtain sharp bounds for the diameter and connectivity of X(G) in terms of the corresponding invariant of G.     

Behaviour of doubly connected minimal surfaces at the edges of the support surface

This paper is the second part of our investigations on doubly connected minimal surfaces which are stationary in a boundary configuration (G, S) (\Gamma, S) in \Bbb R ³ \Bbb R ^3 . The support surface S is a vertical cylinder above a simple closed polygon P(S) P(S) in the x,y-plane. The surrounding Jordan curve G \Gamma is chosen as a generalized graph above its convex projection curve P(G) P(\Gamma) . In [23] we have proved the existence of nonparametric minimal surfaces X of annulus type spanning such boundary configurations. We study the behaviour of these minimal surfaces at the edges of the support surface S. In particular we discuss the phenomenon of edge-creeping, i. e. the fact that the free trace of X may attach to an edge of S in a full interval. We prove that a solution X cuts any intruding edge of S perpendicularly. On the other hand, we derive a condition which forces X to exhibit the edge-creeping behaviour. Depending on the symmetries of (G, S) (\Gamma, S) we give bounds on the number of edges where edge-creeping occurs. Let (x,y,Z (x,y)) (x,y,\hbox {Z} (x,y)) for (x,y) ? G (x,y)\in G be the nonparametric representation of X. Then at every vertex Q of P(S) P(S) the radial limits of Z from all directions in G exist.     

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.     

Circular colorings of weighted graphs

Suppose that G is a finite simple graph and w is a weight function which assigns to each vertex of G a nonnegative real number. Let C be a circle of length t. A t-circular coloring of (G, w) is a mapping Δ of the vertices of G to arcs of C such that Δ(x)∩Δ(y) = 0 if (x, y) ∈ E(G) and Δ(x) has length w(x). The circular-chromatic number of (G, w) is the least t for which there is a t-circular coloring of (G, w). This paper discusses basic properties of circular chromatic number of a weighted graph and relations between this parameter and other graph parameters. We are particularly interested in graphs G for which the circular-chromatic number of (G, w) is equal to the fractional clique weight of (G, w) for arbitrary weight function w. We call such graphs star-superperfect. We prove that odd cycles and their complements are star-superperfect. We then prove a theorem about the circular chromatic number of lexicographic product of graphs which provides a tool of constructing new star-superperfect graphs from old ones. © 1996 John Wiley & Sons, Inc.     

Archimedean ϕ ‐tolerance graphs

Let ? be a symmetric binary function, positive valued on positive arguments. A graph G = (V,E) is a ?‐tolerance graph if each vertex υ ∈ V can be assigned a closed interval I_υ and a positive tolerance t_υ so that xy ∈ E ? | I_x ∩ I_y|≥ ? (t_x,t_y). An Archimedean function has the property of tending to infinity whenever one of its arguments tends to infinity. Generalizing a known result of [15] for trees, we prove that every graph in a large class (which includes all chordless suns and cacti and the complete bipartite graphs K_2,k) is a ?‐tolerance graph for all Archimedean functions ?. This property does not hold for most graphs. Next, we present the result that every graph G can be represented as a ?_G‐tolerance graph for some Archimedean polynomial ?_G. Finally, we prove that there is a ?universal”? Archimedean function ? ^* such that every graph G is a ?^*‐tolerance graph. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 179–194, 2002     

Total weight choosability of graphs

A graph G = (V, E) is called (k, k′)‐total weight choosable if the following holds: For any total list assignment L which assigns to each vertex x a set L(x) of k real numbers, and assigns to each edge e a set L(e) of k′ real numbers, there is a mapping f: V∪E→? such that f(y)∈L(y) for any y∈V∪Eand for any two adjacent vertices x, x′, . We conjecture that every graph is (2, 2)‐total weight choosable and every graph without isolated edges is (1, 3)‐total weight choosable. It follows from results in [7] that complete graphs, complete bipartite graphs, trees other than K₂ are (1, 3)‐total weight choosable. Also a graph G obtained from an arbitrary graph H by subdividing each edge with at least three vertices is (1, 3)‐total weight choosable. This article proves that complete graphs, trees, generalized theta graphs are (2, 2)‐total weight choosable. We also prove that for any graph H, a graph G obtained from H by subdividing each edge with at least two vertices is (2, 2)‐total weight choosable as well as (1, 3)‐total weight choosable. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:198‐212, 2011     

Strengthening Erdös–Pósa property for minor‐closed graph classes

Let ?? and ?? be graph classes. We say that ?? has the Erd?s–Pósa property for ?? if for any graph G ∈??, the minimum vertex covering of all ??‐subgraphs of G is bounded by a function f of the maximum packing of ??‐subgraphs in G (by ??‐subgraph of G we mean any subgraph of G that belongs to ??). Robertson and Seymour [J Combin Theory Ser B 41 (1986), 92–114] proved that if ?? is the class of all graphs that can be contracted to a fixed planar graph H, then ?? has the Erd?s–Pósa property for the class of all graphs with an exponential bounding function. In this note, we prove that this function becomes linear when ?? is any non‐trivial minor‐closed graph class. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:235‐240, 2011     

Score vectors of tournaments

A tournament T on any set X is a dyadic relation such that for any x, y ∈ X (a) (x, x) ? T and (b) if x ≠ y then (x, y) ∈ T iff (y, x) ? T. The score vector of T is the cardinal valued function defined by R(x) = |{y ∈ X : (x, y) ∈ T}|. We present theorems for infinite tournaments analogous to Landau's necessary and sufficient conditions that a vector be the score vector for some finite tournament. Included also is a new proof of Landau's theorem based on a simple application of the “marriage” theorem.     

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.     

Preperfect graphs

We say that a vertexx of a graph is predominant if there exists another vertexy ofG such that either every maximum clique ofG containingy containsx or every maximum stable set containingx containsy. A graph is then called preperfect if every induced subgraph has a predominant vertex. We show that preperfect graphs are perfect, and that several well-known classes of perfect graphs are preperfect. We also derive a new characterization of perfect graphs.     

The universality of Hom complexes of graphs

It is shown that given a connected graph T with at least one edge and an arbitrary finite simplicial complex X, there is a graph G such that the complex Hom(T,G) is homotopy equivalent to X. The proof is constructive, and uses a nerve lemma. Along the way several results regarding Hom complexes, exponentials of graphs, and subdivisions are established that may be of independent interest.     

Visibility Graphs of Point Sets in the Plane

The visibility graph of a discrete point set X⊂ℝ² has vertex set X and an edge xy for every two points x,y∈X whenever there is no other point in X on the line segment between x and y. We show that for every graph G, there is a point set X∈ℝ², such that the subgraph of induced by X is isomorphic to G. As a consequence, we show that there are visibility graphs of arbitrary high chromatic number with clique number 6 settling a question by Kára, Pór and Wood. Supported by the DFG Research Center Matheon (FZT86).