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     

Coverings of the Vertices of a Graph by Small Cycles

Given a graph G with n vertices, we call c_k(G) the minimum number of elementary cycles of length at most k necessary to cover the vertices of G. We bound c_k(G) from the minimum degree and the order of the graph.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

Random Graph Coverings I: General Theory and Graph Connectivity

In this paper we describe a simple model for random graphs that have an n-fold covering map onto a fixed finite base graph. Roughly, given a base graph G and an integer n, we form a random graph by replacing each vertex of G by a set of n vertices, and joining these sets by random matchings whenever the corresponding vertices are adjacent in G. The resulting graph covers the original graph in the sense that the two are locally isomorphic. We suggest possible applications of the model, such as constructing graphs with extremal properties in a more controlled fashion than offered by the standard random models, and also "randomizing" given graphs. The main specific result that we prove here (Theorem 1) is that if is the smallest vertex degree in G, then almost all n-covers of G are -connected. In subsequent papers we will address other graph properties, such as girth, expansion and chromatic number. Received June 21, 1999/Revised November 16, 2000 RID="*" ID="*" Work supported in part by grants from the Israel Academy of Aciences and the Binational Israel-US Science Foundation.     

The endomorphism spectrum of an ordered set

Theendomorphism spectrum of an ordered setP, spec(P)={|f(P)|:f End(P)} andspectrum number, sp(P)=max(spec(P)\{|P|}) are introduced. It is shown that |P|>(1/2)n(n – 1) ^{n – 1} implies spec(P) = {1, 2, ...,n} and that if a projective plane of ordern exists, then there is an ordered setP of size 2n ²+2n+2 with spec(P)={1, 2, ..., 2n+2, 2n+4}. Lettingh(n)=max{|P|: sp(P)n}, it follows thatc ₁ n ²h(n)c ₂ n ⁿ⁺¹ for somec ₁ andc ₂. The lower bound disproves the conjecture thath(n)2n. It is shown that if |P| – 1 spec(P) thenP has a retract of size |P| – 1 but that for all there is a bipartite ordered set with spec(P) = {|P| – 2, |P| – 4, ...} which has no proper retract of size|P| – . The case of reflexive graphs is also treated.Partially supported by a grant from the NSERC.Partially supported by a grant from the NSERC.     

ASYMPTOTIC BOUNDS FOR IRREDUNDANT RAMSEY NUMBERS

Abstract

The irredundant Ramsey number s(m,n) is the smallest N such that in every red-blue colouring of the edges of K_N , either the blue graph contains an m-element irredundant set or the red graph contains an n-element irredundant set. We prove an asymptotic lower bound for s(m, n).     

Vertex-Colouring Edge-Weightings

A weighting w of the edges of a graph G induces a colouring of the vertices of G where the colour of vertex v, denoted c_v, is . We show that the edges of every graph that does not contain a component isomorphic to K₂ can be weighted from the set {1, . . . ,30} such that in the resulting vertex-colouring of G, for every edge (u,v) of G, c_u ≠c_v.     

The roots of <Emphasis Type="Italic">σ</Emphasis>-polynomials

Let G be a connected graph. We denote by σ(G,x) and δ(G) respectively the σ-polynomial and the edge-density of G, where . If σ(G,x) has at least an unreal root, then G is said to be a σ-unreal graph. Let δ(n) be the minimum edgedensity over all n vertices graphs with σ-unreal roots. In this paper, by using the theory of adjoint polynomials, a negative answer to a problem posed by Brenti et al. is given and the following results are obtained: For any positive integer a and rational number 0≤c≤1, there exists at least a graph sequence {G _i}_1≤i≤a such that G _i is σ-unreal and δ(G _i)→c as n→∞ for all 1 ≤i≤a, and moreover, δ(n)→0 as n→∞. Supported by the National Natural Science Foundation of China (10061003) and the Science Foundation of the State Education Ministry of China.     

Subgraphs of colour-critical graphs

Some problems and results on the distribution of subgraphs in colour-critical graphs are discussed. In section 3 arbitrarily largek-critical graphs withn vertices are constructed such that, in order to reduce the chromatic number tok−2, at leastc _k n ² edges must be removed. In section 4 it is proved that a 4-critical graph withn vertices contains at mostn triangles. Further it is proved that ak-critical graph which is not a complete graph contains a (k−1)-critical graph which is not a complete graph.     

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     

Random Matchings in Regular Graphs

d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x. We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) : Theorem. For any d-regular graph G, (a) , so that , (b) , where the rates of convergence depend only on d. Received: April 12, 1996     

Two-point concentration in random geometric graphs

A random geometric graph G _n is constructed by taking vertices X ₁,…,X _n ∈ℝ ^d at random (i.i.d. according to some probability distribution ν with a bounded density function) and including an edge between X _i and X _j if ‖X _i -X _j ‖ < r where r = r(n) > 0. We prove a conjecture of Penrose ([14]) stating that when r=r(n) is chosen such that nr ^d = o(lnn) then the probability distribution of the clique number ω(G _n ) becomes concentrated on two consecutive integers and we show that the same holds for a number of other graph parameters including the chromatic number χ(G _n ). The author was partially supported by EPSRC, the Department of Statistics, Bekkerla-Bastide fonds, Dr. Hendrik Muller’s Vaderlandsch fonds, and Prins Bernhard Cultuurfonds.     

Embedding nearly-spanning bounded degree trees

We derive a sufficient condition for a sparse graph G on n vertices to contain a copy of a tree T of maximum degree at most d on (1 − ε)n vertices, in terms of the expansion properties of G. As a result we show that for fixed d ≥ 2 and 0 < ε < 1, there exists a constant c = c(d, ε) such that a random graph G(n, c/n) contains almost surely a copy of every tree T on (1 − ε)n vertices with maximum degree at most d. We also prove that if an (n, D, λ)-graph G (i.e., a D-regular graph on n vertices all of whose eigenvalues, except the first one, are at most λ in their absolute values) has large enough spectral gap D/λ as a function of d and ε, then G has a copy of every tree T as above. Research supported in part by a USA-Israeli BSF grant, by NSF grant CCR-0324906, by a Wolfensohn fund and by the State of New Jersey. Research supported in part by USA-Israel BSF Grant 2002-133, and by grants 64/01 and 526/05 from the Israel Science Foundation. Research supported in part by NSF CAREER award DMS-0546523, NSF grant DMS-0355497, USA-Israeli BSF grant, and by an Alfred P. Sloan fellowship.     

Birth control for giants

The standard Erdős-Rényi model of random graphs begins with n isolated vertices, and at each round a random edge is added. Parametrizing n/2 rounds as one time unit, a phase transition occurs at time t = 1 when a giant component (one of size constant times n) first appears. Under the influence of statistical mechanics, the investigation of related phase transitions has become an important topic in random graph theory. We define a broad class of graph evolutions in which at each round one chooses one of two random edges {v ₁, v ₂}, {v ₃, v ₄} to add to the graph. The selection is made by examining the sizes of the components of the four vertices. We consider the susceptibility S(t) at time t, being the expected component size of a uniformly chosen vertex. The expected change in S(t) is found which produces in the limit a differential equation for S(t). There is a critical time t _c so that S(t) → ∞ as t approaches t _c from below. We show that the discrete random process asymptotically follows the differential equation for all subcritical t < t _c . Employing classic results of Cramér on branching processes we show that the component sizes of the graph in the subcritical regime have an exponential tail. In particular, the largest component is only logarithmic in size. In the supercritical regime t > t _c we show the existence of a giant component, so that t = t _c may be fairly considered a phase transition. Computer aided solutions to the possible differential equations for susceptibility allow us to establish lower and upper bounds on the extent to which we can either delay or accelerate the birth of the giant component. Research supported by the Australian Research Council, the Canada Research Chairs Program and NSERC. Research partly carried out while the author was at the Department of Mathematics and Statistics, University of Melbourne.     

On entropy-preserving stochastic averages

When an n×n doubly stochastic matrix A acts on Rⁿ on the left as a linear transformation and P is an n-long probability vector, we refer to the new probability vector AP as the stochastic average of the pair (A,P). Let Γ_n denote the set of pairs (A,P) whose stochastic average preserves the entropy of P:H(AP)=H(P). Γ_n is a subset of B_n×Σ_n where B_n is the Birkhoff polytope and Σ_n is the probability simplex.We characterize Γ_n and determine its geometry, topology,and combinatorial structure. For example, we find that (A,P)∈Γ_n if and only if A^tAP=P. We show that for any n, Γ_n is a connected set, and is in fact piecewise-linearly contractible in B_n×Σ_n. We write Γ_n as a finite union of product subspaces, in two distinct ways. We derive the geometry of the fibers (A,·) and (·,P) of Γ_n. Γ₃ is worked out in detail. Our analysis exploits the convexity of xlogx and the structure of an efficiently computable bipartite graph that we associate to each ds-matrix. This graph also lets us represent such a matrix in a permutation-equivalent, block diagonal form where each block is doubly stochastic and fully indecomposable.     

A Greedy Partition Lemma for directed domination

A directed dominating set in a directed graph D is a set S of vertices of V such that every vertex u∈V(D)?S has an adjacent vertex v in S with v directed to u. The directed domination number of D, denoted by γ(D), is the minimum cardinality of a directed dominating set in D. The directed domination number of a graph G, denoted Γ_d(G), is the maximum directed domination number γ(D) over all orientations D of G. The directed domination number of a complete graph was first studied by Erd?s [P. Erd?s On a problem in graph theory, Math. Gaz. 47 (1963) 220–222], albeit in a disguised form. In this paper we prove a Greedy Partition Lemma for directed domination in oriented graphs. Applying this lemma, we obtain bounds on the directed domination number. In particular, if α denotes the independence number of a graph G, we show that α≤Γ_d(G)≤α(1+2ln(n/α)).     

Mutually Independent Hamiltonian Connectivity of (n, k)-Star Graphs

A graph G is hamiltonian connected if there exists a hamiltonian path joining any two distinct nodes of G. Two hamiltonian paths and of G from u to v are independent if u = u ₁ = v ₁, v = u _v(G) = v _v(G) , and u _i ≠ v _i for every 1 < i < v(G). A set of hamiltonian paths, {P ₁, P ₂, . . . , P _k }, of G from u to v are mutually independent if any two different hamiltonian paths are independent from u to v. A graph is k mutually independent hamiltonian connected if for any two distinct nodes u and v, there are k mutually independent hamiltonian paths from u to v. The mutually independent hamiltonian connectivity of a graph G, IHP(G), is the maximum integer k such that G is k mutually independent hamiltonian connected. Let n and k be any two distinct positive integers with n–k ≥ 2. We use S _n,k to denote the (n, k)-star graph. In this paper, we prove that IHP(S _n,k ) = n–2 except for S _4,2 such that IHP(S _4,2) = 1.      

Hamiltonian path saturated graphs with small size

A graph G is said to be hamiltonian path saturated (HPS for short), if G has no hamiltonian path but any addition of a new edge in G creates a hamiltonian path in G. It is known that an HPS graph of order n has size at most and, for n?6, the only HPS graph of order n and size is K_n-1∪K₁. Denote by sat(n,HP) the minimum size of an HPS graph of order n. We prove that sat(n,HP)?⌊(3n-1)/2⌋-2. Using some properties of Isaacs’ snarks we give, for every n?54, an HPS graph G_n of order n and size ⌊(3n-1)/2⌋. This proves sat(n,HP)?⌊(3n-1)/2⌋ for n?54. We also consider m-path cover saturated graphs and P_m-saturated graphs with small size.     

A Construction of Uniquely C4-free colourable Graphs

Abstract

An F-free colouring of a graph G is a partition {V₁,V₂,…,V_n} of the vertex set V(G) of G such that F is not an induced subgraph of G[V_i] for each i. A graph is uniquely F-free colourable if any two .F-free colourings induce the same partition of V(G). We give a constructive proof that uniquely C₄-free colourable graphs exist.