On Four-Connecting a Triconnected Graph

We consider the problem of finding a smallest set of edges whose addition four-connects a triconnected graph. This is a fundamental graph-theoretic problem that has applications in designing reliable networks and improving statistical database security. We present an O(n · α(m, n) + m)-time algorithm for four-connecting an undirected graph G that is triconnected by adding the smallest number of edges, where n and m are the number of vertices and edges in G, respectively, and α(m, n) is the inverse Ackermann function. This is the first polynomial time algorithm to solve this problem exactly.In deriving our algorithm, we present a new lower bound for the number of edges needed to four-connect a triconnected graph. The form of this lower bound is different from the form of the lower bound known for biconnectivity augmentation and triconnectivity augmentation. Our new lower bound applies for arbitrary k and gives a tighter lower bound than the one known earlier for the number of edges needed to k-connect a (k − 1)-connected graph. For k = 4, we show that this lower bound is tight by giving an efficient algorithm to find a set of edges whose size equals the new lower bound and whose addition four-connects the input triconnected graph.     

On cycle—Complete graph ramsey numbers

A new upper bound is given for the cycle-complete graph Ramsey number r(C_m, K_n), the smallest order for a graph which forces it to contain either a cycle of order m or a set of n independent vertices. Then, another cycle-complete graph Ramsey number is studied, namely r(?C_m, K_n) the smallest order for a graph which forces it to contain either a cycle of order / for some / satisfying 3?/?m or a set of n independent vertices. We obtain the exact value of r(?C_m K_n) for all m > n and an upper bound which applies when m is large in comparison with log n.     

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).     

Diameter, connectivity, and phase transition of the uniform random intersection graph

We study properties of the uniform random intersection graph model G(n,m,d). We find asymptotic estimates on the diameter of the largest connected component of the graph near the phase transition and connectivity thresholds. Moreover we manage to prove an asymptotically tight bound for the connectivity and phase transition thresholds for all possible ranges of d, which has not been obtained before. The main motivation of our research is the usage of the random intersection graph model in the studies of wireless sensor networks.     

The Crossing Number of C(mk;{1, k})

Calculating the crossing number of a given graph is, in general, an elusive problem. Garey and Johnson have proved that the problem of determining the crossing number of an arbitrary graph is NP-complete. The crossing number of a network(graph) is closely related to the minimum layout area required for the implementation of a VLSI circuit for that network. With this important application in mind, it makes most sense to analyze the the crossing number of graphs with good interconnection properties, such as the circulant graphs. In this paper we study the crossing number of the circulant graph C(mk;{1,k}) for m3, k3, give an upper bound of cr(C(mk;{1,k})), and prove that cr(C(3k;{1,k}))=k.Research supported by Chinese Natural Science Foundation     

New upper bounds on harmonious colorings

We present an improved upper bound on the harmonious chromatic number of an arbitrary graph. We also consider ?fragmentable”? classes of graphs (an example is the class of planar graphs) that are, roughly speaking, graphs that can be decomposed into bounded-sized components by removing a small proportion of the vertices. We show that for such graphs of bounded degree the harmonious chromatic number is close to the lower bound (2m)^1/2, where m is the number of edges.     

Maximum matchings in a regular graph of specified connectivity and bounded order

Upper bounds are placed on the order of a k-regular m-connected graph G that produce a lower bound on the number of independent edges in G. As a corollary, we obtain the order of a smallest k-regular m-connected graph which has no 1-factor.     

Maximum pebbling number of graphs of diameter three

Given a configuration of pebbles on the vertices of a graph G, a pebbling move consists of taking two pebbles off some vertex v and putting one of them back on a vertex adjacent to v. A graph is called pebbleable if for each vertex v there is a sequence of pebbling moves that would place at least one pebble on v. The pebbling number of a graph G is the smallest integer m such that G is pebbleable for every configuration of m pebbles on G. We prove that the pebbling number of a graph of diameter 3 on n vertices is no more than (3/2)n + O(1), and, by explicit construction, that the bound is sharp. © 2006 Wiley Periodicals, Inc. J Graph Theory     

Efficient and Practical Algorithms for Sequential Modular Decomposition

A module of an undirected graph G = (V, E) is a set X of vertices that have the same set of neighbors in V\X. The modular decomposition is a unique decomposition of the vertices into nested modules. We give a practical algorithm with an O(n + mα(m, n)) time bound and a variant with a linear time bound.     

[a,b]-factorization of a graph

Let a and b be integers such that 0 ? a ? b. Then a graph G is called an [a, b]-graph if a ? d_G(x) ? b for every x ? V(G), and an [a, b]-factor of a graph is defined to be its spanning subgraph F such that a ? d_F(x) ? b for every vertex x, where d_G(x) and d_F(x) denote the degrees of x in G and F, respectively. If the edges of a graph can be decomposed into [a.b]-factors then we say that the graph is [2a, 2a]-factorable. We prove the following two theorems: (i) a graph G is [2a, 2b)-factorable if and only if G is a [2am,2bm]-graph for some integer m, and (ii) every [8m + 2k, 10m + 2k]-graph is [1,2]-factorable.     

Solution of a covering problem related to labelled tournaments

Suppose we have a tournament with edges labelled so that the edges incident with any vertex have at most k distinct labels (and no vertex has outdegree 0). Let m be the minimal size of a subset of labels such that for any vertex there exists an outgoing edge labelled by one of the labels in the subset. It was known that m ≤ (^k+1₂) for any tournament. We show that this bound is almost best possible, by a probabilistic construction of tournaments with m = O(k²/log k). We give explicit tournaments with m = k^2−o(1). If the number of vertices is bounded by N < 2^k₁ we have a better upper bound of m = O(k log N), which is again almost optimal. We also consider a relaxation of this problem in which instead of the size of a subset of labels we minimize the total weight of a fractional set with analogous properties. In that case the optimal bound is 2k − 1. © 1996 John Wiley & Sons, Inc.     

A construction of an infinite family of 2-arc transitive polygonal graphs of arbitrary even girth

A near-polygonal graph is a graph Γ which has a set C\mathcal{C} of m-cycles for some positive integer m such that each 2-path of Γ is contained in exactly one cycle in C\mathcal{C}. If m is the girth of Γ, then the graph is called polygonal. We provide a construction of an infinite family of polygonal graphs of arbitrary even girth with 2-arc transitive automorphism groups, showing that there are infinitely many 2-arc transitive polygonal graphs of every girth.     

Asymptotic bounds for irredundant and mixed Ramsey numbers

The irredundant Ramsey number s(m, n) is the smallest N such that in every red-blue coloring 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. The definition of the mixed Ramsey number t(m, n) differs from s(m, n) in that the n-element irredundant set is replaced by an n-element independent set. We prove asymptotic lower bounds for s(n, n) and t(m, n) (with m fixed and n large) and a general upper bound for t(3, n). © 1993 John Wiley & Sons, Inc.     

On the Interval Number of a Triangulated Graph

The interval number of a simple undirected graph G, denoted i(G), is the least nonnegative integer r for which we can assign to each vertex in G a collection of at most r intervals on the real line such that two distinct vertices v and w of G are adjacent if and only if some interval for v intersects some interval for w. For triangulated graphs G, we consider the problem of finding a sharp upper bound for the interval number of G in terms of its clique number ω(G). The following partial results are proved. (1) For each triangulated graph G, i(G) ? ?ω(G)/2? + 1, and this is best possible for 2 ? ω(G) ? 6. (2) For each integer m ? 2, there exists a triangulated graph G with ω(G) = m and i(G) > m^1/2.     

On the multiplicity of Laplacian eigenvalues for unicyclic graphs

Let G be a connected graph of order n and U a unicyclic graph with the same order. We firstly give a sharp bound for m_G(μ), the multiplicity of a Laplacian eigenvalue μ of G. As a straightforward result, m_U(1) ? n ? 2. We then provide two graph operations (i.e., grafting and shifting) on graph G for which the value of m_G(1) is nondecreasing. As applications, we get the distribution of m_U (1) for unicyclic graphs on n vertices. Moreover, for the two largest possible values of m_U(1) ∈ {n ? 5, n ? 3}, the corresponding graphs U are completely determined.

     

The spanning subgraphs of eulerian graphs

It is shown that a connected graph G spans an eulerian graph if and only if G is not spanned by an odd complete bigraph K(2_m + 1, 2n + 1). A disconnected graph spans an eulerian graph if and only if it is not the union of the trivial graph with a complete graph of odd order. Exact formulas are obtained for the number of lines which must be added to such graphs in order to get eulerian graphs.     

Defective colorings of graphs in surfaces: Partitions into subgraphs of bounded valency

We call a graph (m, k)-colorable if its vertices can be colored with m colors in such a way that each vertex is adjacent to at most k vertices of the same color as itself. For the class of planar graphs, and the class of outerplanar graphs, we determine all pairs (m, k) such that every graph in the class is (m, k)-colorable. We include an elementary proof (not assuming the truth of the four-color theorem) that every planar graph is (4, 1)-colorable. Finally, we prove that, for each compact surface S, there is an integer k = k(S) such that every graph in S can be (4, k)-colored; we conjecture that 4 can be replaced by 3 in this statement.     

An analysis of some linear graph layout heuristics

The worst-case performances of some heuristics for the fixed linear crossing number problem (FLCNP) are analyzed. FLCNP is similar to the 2-page book crossing number problem in which the vertices of a graph are optimally placed on a horizontal “node line” in the plane, each edge is drawn as an arc in one half-plane (page), and the objective is to minimize the number of edge crossings. In FLCNP, the order of the vertices along the node line is predetermined and fixed. FLCNP belongs to the class of NP-hard optimization problems Masuda et al., 1990. In this paper we show that for each of the heuristics described, there exist classes of n-vertex, m-edge graphs which force it to obtain a number of crossings which is a function of n or m when the optimal number is a small constant. This leaves open the problem of finding a heuristic with a constant error bound for the problem.     

On connectivities of tree graphs

Let T(G) be the tree graph of a graph G with cycle rank r. Then κ(T(G)) ? m(G) ? r, where κ(T(G)) and m(G) denote the connectivity of T(G) and the length of a minimum cycle basis for G, respectively. Moreover, the lower bound of m(G) ? r is best possible.     

Pagenumber of complete bipartite graphs

Given an ordering of the vertices of a graph around a circle, a page is a collection of edges forming noncrossing chords. A book embedding is a circular permutation of the vertices together with a partition of the edges into pages. The pagenumber t(G) (also called book thickness) is the minimum number of pages in a book embedding of G. We present a general construction showing t(K_m,n) ? ?(m + 2n)/4?, which we conjecture optimal. We prove a result suggesting this is optimal for m ? 2n ? 3. For the most difficult case m = n, we consider vertex permutations that are regular, i.e., place vertices from each partite set into runs of equal size. Book embeddings with such orderings require ?(7n ? 2)/9? pages, which is achievable. The general construction uses fewer pages, but with an irregular ordering.