Path extendable graphs

A pathP in a graphG is said to beextendable if there exists a pathP’ inG with the same endvertices asP such thatV(P)⊆V (P’) and |V(P’)|=|V(P)|+1. A graphG ispath extendable if every nonhamiltonian path inG is extendable. We investigate the extent to which known sufficient conditions for a graph to be hamiltonian-connected imply the extendability of paths in the graph. Several theorems are proved: for example, it is shown that ifG is a graph of orderp in which the degree sum of each pair of non-adjacent vertices is at leastp+1 andP is a nonextendable path of orderk inG thenk≤(p+1)/2 and 〈V (P)〉≅K _k orK _k −e. As corollaries of this we deduce that if δ(G)≥(p+2)/2 or if the degree sum of each pair of nonadjacent vertices inG is at least (3p−3)/2 thenG is path extendable, which strengthen results of Williamson [13].     

Free multiflows in bidirected and skew-symmetric graphs

A graph (digraph) G=(V,E) with a set T⊆V of terminals is called inner Eulerian if each nonterminal node v has even degree (resp. the numbers of edges entering and leaving v are equal). Cherkassky and Lovász, independently, showed that the maximum number of pairwise edge-disjoint T-paths in an inner Eulerian graph G is equal to , where λ(s) is the minimum number of edges whose removal disconnects s and T-{s}. A similar relation for inner Eulerian digraphs was established by Lomonosov. Considering undirected and directed networks with “inner Eulerian” edge capacities, Ibaraki, Karzanov, and Nagamochi showed that the problem of finding a maximum integer multiflow (where partial flows connect arbitrary pairs of distinct terminals) is reduced to O(logT) maximum flow computations and to a number of flow decompositions.In this paper we extend the above max-min relation to inner Eulerian bidirected graphs and inner Eulerian skew-symmetric graphs and develop an algorithm of complexity for the corresponding capacitated cases. In particular, this improves the best known bound for digraphs. Our algorithm uses a fast procedure for decomposing a flow with O(1) sources and sinks in a digraph into the sum of one-source-one-sink flows.     

Crossing graphs of fiber-complemented graphs

Fiber-complemented graphs form a vast non-bipartite generalization of median graphs. Using a certain natural coloring of edges, induced by parallelism relation between prefibers of a fiber-complemented graph, we introduce the crossing graph of a fiber-complemented graph G as the graph whose vertices are colors, and two colors are adjacent if they cross on some induced 4-cycle in G. We show that a fiber-complemented graph is 2-connected if and only if its crossing graph is connected. We characterize those fiber-complemented graphs whose crossing graph is complete, and also those whose crossing graph is chordal.     

On kernels in perfect graphs

A kernel of a digraphD is a set of vertices which is both independent and absorbant. In 1983, C. Berge and P. Duchet conjectured that an undirected graphG is perfect if and only if the following condition is fulfilled: ifD is an orientation ofG (where pairs of opposite arcs are allowed) and if every clique ofD has a kernel thenD has a kernel. We prove here the conjecture for the complements of strongly perfect graphs and establish that a minimal counterexample to the conjecture is not a complete join of an independent set with another graph.     

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.     

Cycles in weighted graphs

A weighted graph is one in which each edgee is assigned a nonnegative numberw(e), called the weight ofe. The weightw(G) of a weighted graphG is the sum of the weights of its edges. In this paper, we prove, as conjectured in [2], that every 2-edge-connected weighted graph onn vertices contains a cycle of weight at least 2w(G)/(n–1). Furthermore, we completely characterize the 2-edge-connected weighted graphs onn vertices that contain no cycle of weight more than 2w(G)/(n–1). This generalizes, to weighted graphs, a classical result of Erds and Gallai [4].     

Diperfect graphs

Gallai and Milgram have shown that the vertices of a directed graph, with stability number α(G), can be covered by exactly α(G) disjoint paths. However, the various proofs of this result do not imply the existence of a maximum stable setS and of a partition of the vertex-set into paths μ₁, μ₂, ..., μ_k such tht |μ_i ∩S|=1 for alli. Later, Gallai proved that in a directed graph, the maximum number of vertices in a path is at least equal to the chromatic number; here again, we do not know if there exists an optimal coloring (S ₁,S ₂, ...,S _k) and a path μ such that |μ ∩S _i|=1 for alli. In this paper we show that many directed graphs, like the perfect graphs, have stronger properties: for every maximal stable setS there exists a partition of the vertex set into paths which meet the stable set in only one point. Also: for every optimal coloring there exists a path which meets each color class in only one point. This suggests several conjecties similar to the perfect graph conjecture. Dedicated to Tibor Gallai on his seventieth birthday     

Sparse ramsey graphs

IfH is a Ramsey graph for a graphG thenH is rich in copies of the graphG. Here we prove theorems in the opposite direction. We find examples ofH such that copies ofG do not form short cycles inH. This provides a strenghtening also, of the following well-known result of Erdős: there exist graphs with high chromatic number and no short cycles. In particular, we solve a problem of J. Spencer. Dedicated to Paul Erdős on his seventieth birthday     

Monotone paths in ordered graphs

LetV _fin andE _fin resp. denote the classes of graphsG with the property that no matter how we label the vertices (edges, resp.) ofG by members of a linearly ordered set, there will exist paths of arbitrary finite lengths with monotonically increasing labels. The classesV _inf andE _inf are defined similarly by requiring the existence of an infinite path with increasing labels. We proveE _inf ⫋V _inf ⫋V _fin ⫋E _fin. Finally we consider labellings by positive integers and characterize the class corresponding toV _inf.     

Disjoint shortest paths in graphs

It is an interesting problem that how much connectivity ensures the existence ofn disjoint paths joining givenn pairs of vertices, but to get a sharp bound seems to be very difficult. In this paper, we study how muchgeodetic connectivity ensures the existence ofn disjointgeodesics joining givenn pairs of vertices, where a graph is calledk-geodetically connected if the removal of anyk−1 vertices does not change the distance between any remaining vertices.     

Highly linked graphs

A graph with at least 2k vertices is said to bek-linked if, for any choices ₁,...,s _k ,t ₁,...,t _k of 2k distinct vertices there are vertex disjoint pathsP ₁,...,P _k withP _i joinings _i tot _i , 1ik. Recently Robertson and Seymour [16] showed that a graphG isk-linked provided its vertex connectivityk(G) exceeds . We show here thatk(G)22k will do.     

Spanning trees of extended graphs

A generalization of the Prüfer coding of trees is given providing a natural correspondence between the set of codes of spanning trees of a graph and the set of codes of spanning trees of theextension of the graph. This correspondence prompts us to introduce and to investigate a notion ofthe spanning tree volume of a graph and provides a simple relation between the volumes of a graph and its extension (and in particular a simple relation between the spanning tree numbers of a graph and its uniform extension). These results can be used to obtain simple purely combinatorial proofs of many previous results obtained by the Matrix-tree theorem on the number of spanning trees of a graph. The results also make it possible to construct graphs with the maximal number of spanning trees in some classes of graphs.     

H-extension of graphs

We consider the problem of constructing a graphG* from a collection of isomorphic copies of a graphG in such a way that for every two copies ofG, either no vertices or a section graph isomorphic to a graphH is identified. It is shown that ifG can be partitioned into vertex-disjoint copies ofH, thenG* can be made to have at most |H| orbits. A condition onG so thatG* can be vertextransitive is also included.     

Equiarboreal graphs

A graphX is said to beequiarboreal if the number of spanning trees containing a specified edge inX is independent of the choice of edge. We prove that any graph which is a colour class in an association scheme (and thus any distance regular graph) is equiarboreal. We note that a connected equiarboreal graph withM edges andn vertices has edge-connectivity at leastM/(n−1).     

Long paths in sparse random graphs

We consider random graphs withn labelled vertices in which edges are chosen independently and with probabilityc/n. We prove that almost every random graph of this kind contains a path of length ≧(1 −α(c))n where α(c) is an exponentially decreasing function ofc. Dedicated to Tibor Gallai on his seventieth birthday     

Cycle extendability in graphs and digraphs

In 1990, Hendry conjectured that all chordal Hamiltonian graphs are cycle extendable, that is, the vertices of each non-Hamiltonian cycle are contained in a cycle of length one greater. Let A be a symmetric (0,1)-matrix with zero main diagonal such that A is the adjacency matrix of a chordal Hamiltonian graph. Hendry’s conjecture in this case is that every k×k principle submatrix of A that dominates a full cycle permutation k×k matrix is a principle submatrix of a (k+1)×(k+1) principle submatrix of A that dominates a (k+1)×(k+1) full cycle permutation matrix. This article generalizes the concept of cycle-extendability to S-extendable; that is, with S⊆{1,2,…,n} and G a graph on n vertices, G is S-extendable if the vertices of every non-Hamiltonian cycle are contained in a cycle length i greater, where i∈S. We investigate this concept in directed graphs and in particular tournaments, i.e., anti-symmetric matrices with zero main diagonal.     

The cover pebbling number of graphs

A pebbling move on a graph consists of taking two pebbles off of one vertex and placing one pebble on an adjacent vertex. In the traditional pebbling problem we try to reach a specified vertex of the graph by a sequence of pebbling moves. In this paper we investigate the case when every vertex of the graph must end up with at least one pebble after a series of pebbling moves. The cover pebbling number of a graph is the minimum number of pebbles such that however the pebbles are initially placed on the vertices of the graph we can eventually put a pebble on every vertex simultaneously. We find the cover pebbling numbers of trees and some other graphs. We also consider the more general problem where (possibly different) given numbers of pebbles are required for the vertices.     

Optimal clustering of multipartite graphs

Given a graph G=(X,U), the problem dealt within this paper consists in partitioning X into a disjoint union of cliques by adding or removing a minimum number z(G) of edges (Zahn's problem). While the computation of z(G) is NP-hard in general, we show that its computation can be done in polynomial time when G is bipartite, by relating it to a maximum matching problem. When G is a complete multipartite graph, we give an explicit formula specifying z(G) with respect to some structural features of G. In both cases, we give also the structure of all the optimal clusterings of G.     

Expanding graphs contain all small trees

The assertion of the title is formulated and proved. The result is then used to construct graphs with a linear number of edges that, even after the deletion of almost all of their edges or almost all of their vertices, continue to contain all small trees.     

The algebraic connectivity of lollipop graphs

Let C_n,g be the lollipop graph obtained by appending a g-cycle C_g to a pendant vertex of a path on n-g vertices. In 2002, Fallat, Kirkland and Pati proved that for and g?4, α(C_n,g)>α(C_n,g-1). In this paper, we prove that for g?4, α(C_n,g)>α(C_n,g-1) for all n, where α(C_n,g) is the algebraic connectivity of C_n,g.