On the hole index of L(2,1)-labelings of r-regular graphs

An L(2,1)-labeling of a graph G is an assignment of nonnegative integers to the vertices of G so that adjacent vertices get labels at least distance two apart and vertices at distance two get distinct labels. A hole is an unused integer within the range of integers used by the labeling. The lambda number of a graph G, denoted λ(G), is the minimum span taken over all L(2,1)-labelings of G. The hole index of a graph G, denoted ρ(G), is the minimum number of holes taken over all L(2,1)-labelings with span exactly λ(G). Georges and Mauro [On the structure of graphs with non-surjective L(2,1)-labelings, SIAM J. Discrete Math. 19 (2005) 208-223] conjectured that if G is an r-regular graph and ρ(G)?1, then ρ(G) must divide r. We show that this conjecture does not hold by providing an infinite number of r-regular graphs G such that ρ(G) and r are relatively prime integers.     

The 3-choosability of plane graphs of girth 4

A set S of vertices of the graph G is called k-reducible if the following is true: G is k-choosable if and only if G-S is k-choosable. A k-reduced subgraphH of G is a subgraph of G such that H contains no k-reducible set of some specific forms. In this paper, we show that a 3-reduced subgraph of a non-3-choosable plane graph G contains either adjacent 5-faces, or an adjacent 4-face and k-face, where k?6. Using this result, we obtain some sufficient conditions for a plane graph to be 3-choosable. In particular, if G is of girth 4 and contains no 5- and 6-cycles, then G is 3-choosable.     

ON 3-CHOOSABILITY OF PLANE GRAPHS WITHOUT 6-,7- AND 9-CYCLES

The choice number of a graph G,denoted by X1(G),is the minimum number k such that if a list of k colors is given to each vertex of G,there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper,it is showed that X1 (G)≤3 for each plane graph of girth not less than 4 which contains no 6-, 7- and 9-cycles.     

Altitude of regular graphs with girth at least five

The altitude of a graph G is the largest integer k such that for each linear ordering f of its edges, G has a (simple) path P of length k for which f increases along the edge sequence of P. We determine a necessary and sufficient condition for cubic graphs with girth at least five to have altitude three and show that for r?4, r-regular graphs with girth at least five have altitude at least four. Using this result we show that some snarks, including all but one of the Blanus?a type snarks, have altitude three while others, including the flower snarks, have altitude four. We construct an infinite class of 4-regular graphs with altitude four.     

Greedy F-colorings of graphs

Let G=(V,E) be a connected graph. For a symmetric, integer-valued function δ on V×V, where K is an integer constant, N₀ is the set of nonnegative integers, and Z is the set of integers, we define a C-mapping by F(u,v,m)=δ(u,v)+m−K. A coloring c of G is an F-coloring if F(u,v,|c(u)−c(v)|)?0 for every two distinct vertices u and v of G. The maximum color assigned by c to a vertex of G is the value of c, and the F-chromatic number F(G) is the minimum value among all F-colorings of G. For an ordering of the vertices of G, a greedy F-coloring c of s is defined by (1) c(v₁)=1 and (2) for each i with 1?i<n, c(v_i+1) is the smallest positive integer p such that F(v_j,v_i+1,|c(v_j)−p|)?0, for each j with 1?j?i. The greedy F-chromatic number gF(s) of s is the maximum color assigned by c to a vertex of G. The greedy F-chromatic number of G is gF(G)=min{gF(s)} over all orderings s of V. The Grundy F-chromatic number is GF(G)=max{gF(s)} over all orderings s of V. It is shown that gF(G)=F(G) for every graph G and every F-coloring defined on G. The parameters gF(G) and GF(G) are studied and compared for a special case of the C-mapping F on a connected graph G, where δ(u,v) is the distance between u and v and .     

Large faces in 4-critical planar graphs with minimum degree 4

We prove that the size of the largest face of a 4-critical planar graph with 4 is at most one half the number of its vertices. Letf(n) denote the maximum of the sizes of largest faces of all such graphs withn vertices (n sufficiently large). We present an infinite family of graphs that shows .All three authors gratefully acknowledge the support of the National Science and Engineering Research Council of Canada.     

Classes of graphs with minimum skew rank 4

The minimum skew rank of a simple graph G   is the smallest possible rank among all real skew-symmetric matrices whose (i,j)$(i,j)$-entry is nonzero if and only if the edge joining i and j is in G. It is known that a graph has minimum skew rank 2 if and only if it consists of a complete multipartite graph and some isolated vertices. Some necessary conditions for a graph to have minimum skew rank 4 are established, and several families of graphs with minimum skew rank 4 are given. Linear algebraic techniques are developed to show that complements of trees and certain outerplanar graphs have minimum skew rank 4.     

On minimally circular-imperfect graphs

A circular-perfect graph is a graph of which each induced subgraph has the same circular chromatic number as its circular clique number. In this paper, (1) we prove a lower bound on the order of minimally circular-imperfect graphs, and characterize those that attain the bound; (2) we prove that if G is a claw-free minimally circular-imperfect graph such that ω_c(G-x)>ω(G-x) for some x∈V(G), then G=K_(2k+1)/2+x for an integer k; and (3) we also characterize all minimally circular-imperfect line graphs.     

Some remarks on (k−1)-critical subgraphs ofk-critical graphs

A graphG is said to bek-critical if it has chromatic numberk, but every proper subgraph ofG has a (k–1)-coloring. Gallai asked whether every largek-critical graph contains many (k–1)-critical subgraphs. We provide some information concerning this question and some related questions.     

Zero forcing sets and the minimum rank of graphs

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. This paper introduces a new graph parameter, Z(G), that is the minimum size of a zero forcing set of vertices and uses it to bound the minimum rank for numerous families of graphs, often enabling computation of the minimum rank.     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

The choice number of random bipartite graphs

A random bipartite graphG(n, n, p) is obtained by taking two disjoint subsets of verticesA andB of cardinalityn each, and by connecting each pair of verticesaA andbB by an edge randomly and independently with probabilityp=p(n). We show that the choice number ofG(n, n, p) is, almost surely, (1+o(1))log₂(np) for all values of the edge probabilityp=p(n), where theo(1) term tends to 0 asnp tends to infinity.Research supported in part by a USA-Israeli BSF grant, a grant from the Israel Science Foundation, a Sloan Foundation grant No. 96-6-2 and a State of New Jersey grant.Research supported by an IAS/DIMACS Postdoctoral Fellowship.     

The cover-index of infinite graphs

We show that the cover-index of an infinite graph can be expressed in terms of colouring properties of its finite subgraphs when the minimum degree of the graph is finite. We prove that every simple graph with infinite minimum degree contains a tree which is regular of degree and use this to prove that every graph with minimum degree can be decomposed into mutually edge-disjoint spanning subgraphs without ioslated vertices. In particular, the cover-index of a graph equals the minimum degree, when this is infinite.     

The new methods for constructing matching-equivalence graphs

Two graphs G and H with order n are said to be matching-equivalent if and only if the number of r-matchings (i.e., the number of ways in which r disjoint edges can be chosen) is the same for each of the graphs G and H for each r, where 0?r?n. In this paper, the new methods for constructing ‘matching-equivalent’ graphs are given, and some families of non-matching unique graphs are also obtained.     

The list chromatic numbers of some planar graphs

In this paper, the choosability of outerplanar graphs, 1-tree and strong 1-outerplanargraphs have been described completely. A precise upper bound of the list chromatic number of 1-outerplanar graphs is given, and that every 1-outerplanar graph with girth at least 4 is 3-choosable is proved.     

The concentration of the chromatic number of random graphs

We prove that for every constant >0 the chromatic number of the random graphG(n, p) withp=n ^–1/2– is asymptotically almost surely concentrated in two consecutive values. This implies that for any <1/2 and any integer valued functionr(n)O(n ) there exists a functionp(n) such that the chromatic number ofG(n,p(n)) is preciselyr(n) asymptotically almost surely.Research supported in part by a USA Israeli BSF grant and by a grant from the Israel Science Foundation.Research supported in part by a Charles Clore Fellowship.     

On acyclic and unicyclic graphs whose minimum rank equals the diameter

The minimum rank of a graph G is defined as the smallest possible rank over all symmetric matrices governed by G. It is well known that the minimum rank of a connected graph is at least the diameter of that graph. In this paper, we investigate the graphs for which equality holds between minimum rank and diameter, and completely describe the acyclic and unicyclic graphs for which this equality holds.     

Efficient algorithms for finding minimum spanning trees in undirected and directed graphs

Recently, Fredman and Tarjan invented a new, especially efficient form of heap (priority queue). Their data structure, theFibonacci heap (or F-heap) supports arbitrary deletion inO(logn) amortized time and other heap operations inO(1) amortized time. In this paper we use F-heaps to obtain fast algorithms for finding minimum spanning trees in undirected and directed graphs. For an undirected graph containingn vertices andm edges, our minimum spanning tree algorithm runs inO(m logβ (m, n)) time, improved fromO(mβ(m, n)) time, whereβ(m, n)=min {i|log⁽ⁱ⁾ n ≦m/n}. Our minimum spanning tree algorithm for directed graphs runs inO(n logn + m) time, improved fromO(n log n +m log log log_(m/n+2) n). Both algorithms can be extended to allow a degree constraint at one vertex. Research supported in part by National Science Foundation Grant MCS-8302648. Research supported in part by National Science Foundation Grant MCS-8303139. Research supported in part by National Science Foundation Grant MCS-8300984 and a United States Army Research Office Program Fellowship, DAAG29-83-GO020.     

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.