Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

Harmonic trees

A graph G is defined to be harmonic if there is a constant λ (necessarily a natural number) such that, for every vertex v, the sum of the degrees of the neighbors of v equals λd_G (v) where d_G (v) is the degree of v. We show that there is exactly one finite harmonic tree for every λ ε , and we give a recursive construction for all infinite harmonic trees.     

List colourings of planar graphs

A graph G = G(V, E) is called L-list colourable if there is a vertex colouring of G in which the colour assigned to a vertex v is chosen from a list L(v) associated with this vertex. We say G is k-choosable if all lists L(v) have the cardinality k and G is L-list colourable for all possible assignments of such lists. There are two classical conjectures from Erd s, Rubin and Taylor 1979 about the choosability of planar graphs:

every planar graph is 5-choosable and,

there are planar graphs which are not 4-choosable.

We will prove the second conjecture.     

Every tree is 3-equitable

A labeling of a graph is a function f from the vertex set to some subset of the natural numbers. The image of a vertex is called its label. We assign the label |f(u)−f(v)| to the edge incident with vertices u and v. In a k-equitable labeling the image of f is the set {0,1,2,…,k−1}. We require both the vertex labels and the edge labels to be as equally distributed as possible, i.e., if v_i denotes the number of vertices labeled i and e_i denotes the number of edges labeled i, we require |v_i−v_j|1 and |e_i−e_j|1 for every i,j in {0,1,2,…,k−1}. Equitable graph labelings were introduced by I. Cahit as a generalization for graceful labeling. We prove that every tree is 3-equitable.     

An extension theorem for t-designs

In 1994, van Trung (Discrete Math. 128 (1994) 337–348) [9] proved that if, for some positive integers d and h, there exists an S_λ(t,k,v) such that

then there exists an S_λ(v−t+1)(t,k,v+1) having v+1 pairwise disjoint subdesigns S_λ(t,k,v). Moreover, if B_i and B_j are any two blocks belonging to two distinct such subdesigns, then d|B_i∩B_j|<k−h. In 1999, Baudelet and Sebille (J. Combin. Des. 7 (1999) 107–112) proved that if, for some positive integers, there exists an S_λ(t,k,v) such that

where m=min{s,v−k} and n=min{i,t}, then there exists an

having pairwise disjoint subdesigns S_λ(t,k,v). The purpose of this paper is to generalize these two constructions in order to produce a new recursive construction of t-designs and a new extension theorem of t-designs.     

Some results on integral sum graphs

Let Z denote the set of all integers. The integral sum graph of a finite subset S of Z is the graph (S,E) with vertex set S and edge set E such that for u,vS, uvE if and only if u+vS. A graph G is called an integral sum graph if it is isomorphic to the integral sum graph of some finite subset S of Z. The integral sum number of a given graph G, denoted by ζ(G), is the smallest number of isolated vertices which when added to G result in an integral sum graph. Let x denote the least integer not less than the real x. In this paper, we (i) determine the value of ζ(K_n−E(K_r)) for r2n/3−1, (ii) obtain a lower bound for ζ(K_n−E(K_r)) when 2r<2n/3−1 and n5, showing by construction that the bound is sharp when r=2, and (iii) determine the value of ζ(K_r,r) for r2. These results provide partial solutions to two problems posed by Harary (Discrete Math. 124 (1994) 101–108). Finally, we furnish a counterexample to a result on the sum number of K_r,s given by Hartsfiedl and Smyth (Graphs and Matrices, R. Rees (Ed.), Marcel, Dekker, New York, 1992, pp. 205–211).     

Vertices contained in all or in no minimum total dominating set of a tree

A set S of vertices in a graph G is a total dominating set of G if every vertex of G is adjacent to some vertex in S. We characterize the set of vertices of a tree that are contained in all, or in no, minimum total dominating sets of the tree.     

Vertex pancyclic graphs

Let G be a graph of order n. A graph G is called pancyclic if it contains a cycle of length k for every 3kn, and it is called vertex pancyclic if every vertex is contained in a cycle of length k for every 3kn. In this paper, we shall present different sufficient conditions for graphs to be vertex pancyclic.     

Magic Labeling of Disjoint Union Graphs

Let G be a graph with vertex set V (G), edge set E(G) and maximum degree Δ respectively. G is called degree-magic if it admits a labelling of the edges by integers {1, 2, …,|E(G)|} such that for any vertex v the sum of the labels of the edges incident with v is equal to (1+|E(G)|)/2·d(v), where d(v) is the degree of v. Let f be a proper edge coloring of G such that for each vertex v ∈ V (G),|{e:e ∈ E_v, f(e) ≤ Δ/2}|=|{e:e ∈ E_v, f(e) > Δ/2}|, and such an f is called a balanced edge coloring of G. In this paper, we show that if G is a supermagic even graph with a balanced edge coloring and m ≥ 1, then (2m + 1)G is a supermagic graph. If G is a d-magic even graph with a balanced edge coloring and n ≥ 2, then nG is a d-magic graph. Results in this paper generalise some known results.     

Harary's conjectures on integral sum graphs

Let N denote the set of positive integers and Z denote all integers. The (integral) sum graph of a finite subset S N(Z) is the graph (S, E) with uv ε E if and only if u + v ε S. A graph G is said to be an (integral) sum graph if it is isomorphic to the (integral) sum graph of some S N(Z). The (integral) sum number of a given graph G is the smallest number of isolated nodes which when added to G result in an (integral) sum graph.

We show that the integral sum number of a complete graph with n 4 nodes equals 2n − 3, which proves a conjecture of Harary. And we disprove another conjecture of Harary by showing that there are infinitely many trees which are not caterpillars but are integral sum graphs.     

Algorithmic complexity of list colorings

Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → _vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xε_vεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.     

Graphs having distance-n domination number half their order

For any positive integer n and any graph G a set D of vertices of G is a distance-n dominating set, if every vertex vV(G)−D has exactly distance n to at least one vertex in D. The distance-n domination number γ_=n(G) is the smallest number of vertices in any distance-n dominating set. If G is a graph of order p and each vertex in G has distance n to at least one vertex in G, then the distance-n domination number has the upper bound p/2 as Ore's upper bound on the classical domination number. In this paper, a characterization is given for graphs having distance-n domination number equal to half their order, when the diameter is greater or equal 2n−1. With this result we confirm a conjecture of Boland, Haynes, and Lawson.     

Wings and perfect graphs

An edge uv of a graph G is called a wing if there exists a chordless path with vertices u, v, x, y and edges uv, vx, xy. The wing-graph W(G) of a graph G is a graph having the same vertex set as G; uv is an edge in W(G) if and only if uv is a wing in G. A graph G is saturated if G is isomorphic to W(G). A star-cutset in a graph G is a non-empty set of vertices such that G — C is disconnected and some vertex in C is adjacent to all the remaining vertices in C. V. Chvátal proposed to call a graph unbreakable if neither G nor its complement contain a star-cutset. We establish several properties of unbreakable graphs using the notions of wings and saturation. In particular, we obtain seven equivalent versions of the Strong Perfect Graph Conjecture.     

Colouring Steiner systems with specified block colour patterns

We consider colourings of Steiner systems S(2,3,v) and S(2,4,v) in which blocks have prescribed colour patterns, as a refinement of the classical weak colourings. The main question studied is, given an integer k, does there exist a colouring of given type using exactly k colours? For several types of colourings, a complete answer to this question is obtained while for other types, partial results are presented. We also discuss the question of the existence of uncolourable systems.     

Block graphs with unique minimum dominating sets

For any graph G a set D of vertices of G is a dominating set, if every vertex vV(G)−D has at least one neighbor in D. The domination number γ(G) is the smallest number of vertices in any dominating set. In this paper, a characterization is given for block graphs having a unique minimum dominating set. With this result, we generalize a theorem of Gunther, Hartnell, Markus and Rall for trees.     

Characteristic vertices of weighted trees via perron values

We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron value and vector of a nonnegative matrix which can be computed from the branches of T at v. The machinery of Perron-Frobenius theory can then be used to characterize Type I and Type II trees in terms of these Perron values, and to show that if we construct a weighted tree by taking two weighted trees and identifying a vertex of one with a vertex of the other, then any characteristic vertex of the new tree lies on the path joining the characteristic vertices of the two old trees.     

Near vector spaces over GF(q) and (v,q+1,1)-BIBD''s

The usual construction of (v,q+1,1)−BIBD's from vector spaces over GF(q) is generalized to the class of near vector spaces over GF(q). It is shown that every (v,q+1,1)−BIBD can be constructed from a near vector space over GF(q). Some corollaries are: Given a (v₁,q+1,1)−BIBD P₁,B₁ and a (v₂,q+1,1)−BIBD P₂,B₂, there is a ((q−1)v₁v₂+v₁+v₂,q+1,1)−BIBD P₃,B₃ containing P₁,B₁ and P₂,B₂ as disjoint subdesigns. If there is a (v,q+1,1)−BIBD then there is a ((q−1)v+1,q,1)−BIBD. Every finite partial (v,q,1)−BIBD can be embedded in a finite (v′,q+1,1)−BIBD.     

On a straight-line embedding problem of graphs

Let G be a planar graph with n vertices, v be a specified vertex of G, and P be a set of n points in the Euclidian plane in general position. A straight-line embedding of G onto P is an embedding of G onto whose images of vertices are distinct points in P and whose images of edges are (straight) line segments. In this paper, we classify into five classes those pairs of G and v such that for any P and any p P, G has a straight-line embedding onto P which maps v to p. We then show that all graphs in three of the classes indeed have such an embedding. This result gives a solution to a generalized version of the rooted-tree embedding problem raised by M. Perles.     

Bipartite double cover and perfect 2-matching covered graph with its algorithm

Let B(G) denote the bipartite double cover of a non-bipartite graph G with v≥2 vertices and ? edges. We prove that G is a perfect 2-matching covered graph if and only if B(G) is a 1-extendable graph. Furthermore, we prove that B(G) is a minimally 1-extendable graph if and only if G is a minimally perfect 2-matching covered graph and for each e = xy ∈ E(G), there is an independent set S in G such that |Γ_G(S)| = |S| + 1, x ∈S and |Γ_G-xy(S) | = |S|. Then, we construct a digraph D from B(G) or G and show that D is a strongly connected digraph if and only if G is a perfect 2-matching covered graph. So we design an algorithm in O(v?) time that determines whether G is a perfect 2-matching covered graph or not.     

Graph rigidity via Euclidean distance matrices

Let G=(V,E,ω) be an incomplete graph with node set V, edge set E, and nonnegative weights ω_ij's on the edges. Let each edge (v_i,v_j) be viewed as a rigid bar, of length ω_ij, which can rotate freely around its end nodes. A realization of a graph G is an assignment of coordinates, in some Euclidean space, to each node of G. In this paper, we consider the problem of determining whether or not a given realization of a graph G is rigid. We show that each realization of G can be epresented as a point in a compact convex set ; and that a generic realization of G is rigid if and only if its corresponding point is a vertex of Ω, i.e., an extreme point with full-dimensional normal cone.