The edmonds—Gallai decomposition for matchings in locally finite graphs

We show that the Edmonds—Gallai decomposition theorem for matchings in finite graphs generalizes to all locally finite graphs. C.N.R.S. Dedicated to Tibor Gallai on his seventieth birthday     

Finite invariant simplices in infinite graphs

It is shown that ifG is a graph which is contractible or dismantlable or finitely ball-Helly, and without infinite paths; or which is bounded, finitely ball-Helly and without infinite simplices then: (i) any contraction ofG stabilizes a finite simplex; and (ii)G contains a finite simplex which is invariant under any automorphism.     

Judicious partitions of graphs

To 80^th birthday of Paul Erds     

The partial complement of graphs

For a graphG, the switched graphS _v (G) ofG at a vertexv is the graph obtained fromG by deleting the edges ofG incident withv and adding the edges of incident withv. Properties of graphs whereS _v (G) G or are studied. This concept is extended to the partial complementS _H (G) where H . The investigation here centers around the existence of setsH for whichS _H (G) G. A parameter is introduced which measures how near a graph is to being self-complementary.     

A note on 1-factors in graphs

Conditions on a graphG are presented which are sufficient to guarantee thatG–Z contains a 1-factor, whereZ is a set of edges ofG of restricted cardinality. These conditions provide generalizations of several known results and, further, establish the result that ifG is anr-regular, (r–2)-edge-connected graph (r2) of even order andz is an integer with 0zr–1 such thatG contains fewer thanr–z edge cut sets of cardinalityr–2, thenG–Z has a 1-factor for each setZ ofz edges ofG.     

Triples,current graphs and biembeddings

A family of ladder graphs, used by Youngs in his work on the Heawood conjecture, is used to provide constructions of Skolem and related triple systems, triangular biembeddings of certain complete graphs, and genus embeddings of certain complete multipartite graphs.     

Connected graphs containing a given connected graph as a unique greatest common subgraph

Those connected graphsG are determined for which there exist nonisomorphic connected graphs of equal size containingG as a unique greatest common subgraph. Analogous results are also obtained for weakly connected and strongly connected digraphs, as well as for induced subgraphs and induced subdigraphs.This research was supported by a Western Michigan University faculty research fellowship.This research was supported in part by a Western Michigan University research assistantship from the Graduate College and the College of Arts and Sciences.     

Proof of a conjecture of T. Gallai concerning connectivity properties of colour-critical graphs

Tibor Gallai made the following conjecture. LetG be ak-chromatic colour-critical graph. LetL denote the set of those vertices ofG having valencyk−1 and letH be the rest ofV(G). Then the number of components induced byL is not less than the number of components induced byH, providedL ≠ 0. We prove this conjecture in a slightly generalized form. Dedicated to Tibor Gallai on his seventieth birthday     

A class of dimension-skipping graphs

Forn≧6 there exists a graphG with dimG=n, dimG*≧n+2, whereG* isG with a certain edge added.     

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.     

The diameter of random regular graphs

We give asymptotic upper and lower bounds for the diameter of almost everyr-regular graph onn vertices (n → ∞).     

Bounding the diameter of distance-regular graphs

LetG be a connected distance-regular graph with valencyk>2 and diameterd, but not a complete multipartite graph. Suppose that is an eigenvalue ofG with multiplicitym and that±k. We prove that bothd andk are bounded by functions ofm. This implies that, ifm>1 is given, there are only finitely many connected, co-connected distance-regular graphs with an eigenvalue of multiplicitym.This work was supported by NSERC grant A5367.     

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.     

Some remarks on interval graphs

Using simplicial decompositions a new and simple proof of Lekkerkerker-Boland’s criterion for interval graphs is given. Also the infinite case is considered, and the problem is tackled to what extent the representation of a graph as an interval graph is unique. Dedicated to Tibor Gallai on his seventieth birthday     

On minimum secure dominating sets of graphs

A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X/{v}) ? {u} is again a dominating set of G, in which case v is called a defender. The secure domination number of G is the cardinality of a smallest secure dominating set of G. In this paper, we show that every graph of minimum degree at least 2 possesses a minimum secure dominating set in which all vertices are defenders. We also characterise the classes of graphs that have secure domination numbers 1, 2 and 3.     

Counting substructures I: Color critical graphs

Let F be a graph which contains an edge whose deletion reduces its chromatic number. We prove tight bounds on the number of copies of F in a graph with a prescribed number of vertices and edges. Our results extend those of Simonovits (1968) [8], who proved that there is one copy of F, and of Rademacher, Erd?s (1962) [1] and [2] and Lovász and Simonovits (1983) [4], who proved similar counting results when F is a complete graph.One of the simplest cases of our theorem is the following new result. There is an absolute positive constant c such that if n is sufficiently large and 1?q<cn, then every n vertex graph with ⌊n²/4⌋+q edges contains at least

     

赋权图的w密度和w平衡性

The notion of w-density for the graphs with positive weights on vertices and nonnegative weights on edges is introduced. A weighted graph is called w-balanced if its w-density is no less than the w-density of any subgraph of it. In this paper,a good characterization of w-balanced weighted graphs is given. Applying this characterization ,many large w-balanced weighted graphs are formed by combining smaller ones. In the case where a graph is not w-balanced,a polynomial-time algorithm to find a subgraph of maximum w-density is proposed. It is shown that the w-density theory is closely related to the study of SEW(G,w) games.     

RandomlyH-coverable graphs

A graph israndomly matchable if every matching of the graph is contained in a perfect matching. We generalize this notion and say that a graphG israndomly H-coverable if every set of independent subgraphs, each isomorphic toH, that does not cover the vertices ofG can be extended to a larger set of independent copies ofH. Various problems are considered for the situation whereH is a path. In particular, we characterize the graphs that are randomlyP ₃ -coverable.