Critically indecomposable graphs

An undirected graph G=(V,E) with a specific subset X⊂V is called X-critical if G and G(X), induced subgraph on X, are indecomposable but G(V−{w}) is decomposable for every w∈V−X. This is a generalization of critically indecomposable graphs studied by Schmerl and Trotter [J.H. Schmerl, W.T. Trotter, Critically indecomposable partially ordered sets, graphs, tournaments and other binary relational structures, Discrete Mathematics 113 (1993) 191-205] and Bonizzoni [P. Bonizzoni, Primitive 2-structures with the (n−2)-property, Theoretical Computer Science 132 (1994) 151-178], who deal with the case where X is empty.We present several structural results for this class of graphs and show that in every X-critical graph the vertices of V−X can be partitioned into pairs (a₁,b₁),(a₂,b₂),…,(a_m,b_m) such that G(V−{a_j1,b_j1,…,a_jk,b_jk}) is also an X-critical graph for arbitrary set of indices {j₁,…,j_k}. These vertex pairs are called commutative elimination sequence. If G is an arbitrary indecomposable graph with an indecomposable induced subgraph G(X), then the above result establishes the existence of an indecomposability preserving sequence of vertex pairs (x₁,y₁),…,(x_t,y_t) such that x_i,y_i∈V−X. As an application of the commutative elimination sequence of an X-critical graph we present algorithms to extend a 3-coloring (similarly, 1-factor) of G(X) to entire G.     

Simultaneous graph parameters: Factor domination and factor total domination

Let F₁,F₂,…,F_k be graphs with the same vertex set V. A subset S⊆V is a factor dominating set if in every F_i every vertex not in S is adjacent to a vertex in S, and a factor total dominating set if in every F_i every vertex in V is adjacent to a vertex in S. The cardinality of a smallest such set is the factor (total) domination number. In this note, we investigate bounds on the factor (total) domination number. These bounds exploit results on colorings of graphs and transversals of hypergraphs.     

An adaptive memory algorithm for the k-coloring problem

Let G=(V,E) be a graph with vertex set V and edge set E. The k-coloring problem is to assign a color (a number chosen in {1,…,k}) to each vertex of G so that no edge has both endpoints with the same color. The adaptive memory algorithm is a hybrid evolutionary heuristic that uses a central memory. At each iteration, the information contained in the central memory is used for producing an offspring solution which is then possibly improved using a local search algorithm. The so obtained solution is finally used to update the central memory. We describe in this paper an adaptive memory algorithm for the k-coloring problem. Computational experiments give evidence that this new algorithm is competitive with, and simpler and more flexible than, the best known graph coloring algorithms.     

An upper bound for the restrained domination number of a graph with minimum degree at least two in terms of order and minimum degree

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set if every vertex in V−S is adjacent to a vertex in S and to a vertex in V−S. The restrained domination number of G, denoted γ_r(G), is the smallest cardinality of a restrained dominating set of G. We will show that if G is a connected graph of order n and minimum degree δ and not isomorphic to one of nine exceptional graphs, then .     

Sums and k-sums in abelian groups of order k

Let G be an abelian group of order k. How is the problem of minimizing the number of sums from a sequence of given length in G related to the problem of minimizing the number of k-sums? In this paper we show that the minimum number of k-sums for a sequence a₁,…,ar that does not have 0 as a k-sum is attained at the sequence b₁,…,br−k+1,0,…,0, where b₁,…,br−k+1 is chosen to minimise the number of sums without 0 being a sum. Equivalently, to minimise the number of k-sums one should repeat some value k−1 times. This proves a conjecture of Bollobás and Leader, and extends results of Gao and of Bollobás and Leader.     

Two new methods to obtain super vertex-magic total labelings of graphs

Let G=(V,E) be a finite non-empty graph, where V and E are the sets of vertices and edges of G, respectively, and |V|=n and |E|=e. A vertex-magic total labeling (VMTL) is a bijection λ from V∪E to the consecutive integers 1,2,…,n+e with the property that for every v∈V, , for some constant h. Such a labeling is super if λ(V)={1,2,…,n}. In this paper, two new methods to obtain super VMTLs of graphs are put forward. The first, from a graph G with some characteristics, provides a super VMTL to the graph kG graph composed by the disjoint unions of k copies of G, for a large number of values of k. The second, from a graph G₀ which admits a super VMTL; for instance, the graph kG, provides many super VMTLs for the graphs obtained from G₀ by means of the addition to it of various sets of edges.     

On the equality of the partial Grundy and upper ochromatic numbers of graphs

A (proper) k-coloring of a graph G is a partition Π={V₁,V₂,…,V_k} of V(G) into k independent sets, called color classes. In a k-coloring Π, a vertex v∈V_i is called a Grundy vertex if v is adjacent to at least one vertex in color class V_j, for every j, j<i. A k-coloring is called a Grundy coloring if every vertex is a Grundy vertex. A k-coloring is called a partial Grundy coloring if every color class contains at least one Grundy vertex. In this paper we introduce partial Grundy colorings, and relate them to parsimonious proper colorings introduced by Simmons in 1982.     

Line-graphs of cubic graphs are normal

A graph is called normal if its vertex set can be covered by cliques Q₁,Q₂,…,Q_k and also by stable sets S₁,S₂,…,S_l, such that S_i∩Q_j≠∅ for every i,j. This notion is due to Körner, who introduced the class of normal graphs as an extension of the class of perfect graphs. Normality has also relevance in information theory. Here we prove, that the line graphs of cubic graphs are normal.     

A multiplicative inequality for vertex Folkman numbers

Let G be a graph and a₁,…,a_r be positive integers. The symbol G→(a₁,…,a_r) denotes that in every r-coloring of the vertex set V(G) there exists a monochromatic a_i-clique of color i for some i∈{1,…,r}. The vertex Folkman numbers F(a₁,…,a_r;q)=min{|V(G)|:G→(a₁,…,a_r) and K_q?G} are considered. Let a_i, b_i, c_i, i∈{1,…,r}, s, t be positive integers and c_i=a_ib_i, 1?a_i?s,1?b_i?t. Then we prove that

F(c₁,c₂,…,c_r;st+1)?F(a₁,a₂,…,a_r;s+1)F(b₁,b₂,…,b_r;t+1).     

Homogeneoys graphs

Let Γ be a finite graph with vertex set VΓ, and let U, V be arbitrary subsets of VΓ. Γ is homogeneoys (resp. ultrahomogeneous) if whenever the induced subgraphs 〈U〉, 〈V〉 are isomorphic, some isomorphism (resp. every isomorphism) of 〈U〉 onto 〈V〉 extends to an automorphism of Γ. We extend a theorem of Sheehan on ultrahomogeneous graphs to the homogeneous case, and complete his classification of ultrahomogenous graphs.     

Arbitrarily vertex decomposable suns with few rays

A graph G of order n is called arbitrarily vertex decomposable if for each sequence (n₁,…,n_k) of positive integers with n₁+?+n_k=n, there exists a partition (V₁,…,V_k) of the vertex set of G such that V_i induces a connected subgraph of order n_i, for all i=1,…,k. A sun with r rays is a unicyclic graph obtained by adding r hanging edges to r distinct vertices of a cycle. We characterize all arbitrarily vertex decomposable suns with at most three rays. We also provide a list of all on-line arbitrarily vertex decomposable suns with any number of rays.     

Graham’s pebbling conjecture on product of thorn graphs of complete graphs

The pebbling number of a graph G, f(G), is the least n such that, no matter how n pebbles are placed on the vertices of G, we can move a pebble to any vertex by a sequence of pebbling moves, each move taking two pebbles off one vertex and placing one on an adjacent vertex. Let p₁,p₂,…,p_n be positive integers and G be such a graph, V(G)=n. The thorn graph of the graph G, with parameters p₁,p₂,…,p_n, is obtained by attaching p_i new vertices of degree 1 to the vertex u_i of the graph G, i=1,2,…,n. Graham conjectured that for any connected graphs G and H, f(G×H)≤f(G)f(H). We show that Graham’s conjecture holds true for a thorn graph of the complete graph with every by a graph with the two-pebbling property. As a corollary, Graham’s conjecture holds when G and H are the thorn graphs of the complete graphs with every .     

A note on traversing specified vertices in graphs embedded with large representativity

A graph G is said to have property P(2,k) if given any k+2 distinct vertices a,b,v₁,…,v_k, there is a path P in G joining a and b and passing through all of v₁,…,v_k. A graph G is said to have property C(k) if given any k distinct vertices v₁,…,v_k, there is a cycle C in G containing all of v₁,…,v_k. It is shown that if a 4-connected graph G is embedded in an orientable surface Σ (other than the sphere) of Euler genus eg(G,Σ), with sufficiently large representativity (as a function of both eg(G,Σ) and k), then G possesses both properties P(2,k) and C(k).     

Rainbow domination on trees

This paper studies a variation of domination in graphs called rainbow domination. For a positive integer k, a k-rainbow dominating function of a graph G is a function f from V(G) to the set of all subsets of {1,2,…,k} such that for any vertex v with f(v)=0? we have ∪_u∈NG(v)f(u)={1,2,…,k}. The 1-rainbow domination is the same as the ordinary domination. The k-rainbow domination problem is to determine the k-rainbow domination number of a graph G, that is the minimum value of ∑_v∈V(G)|f(v)| where f runs over all k-rainbow dominating functions of G. In this paper, we prove that the k-rainbow domination problem is NP-complete even when restricted to chordal graphs or bipartite graphs. We then give a linear-time algorithm for the k-rainbow domination problem on trees. For a given tree T, we also determine the smallest k such that .     

On the packing chromatic number of some lattices

For a positive integer k, a k-packing in a graph G is a subset A of vertices such that the distance between any two distinct vertices from A is more than k. The packing chromatic number of G is the smallest integer m such that the vertex set of G can be partitioned as V₁,V₂,…,V_m where V_i is an i-packing for each i. It is proved that the planar triangular lattice T and the three-dimensional integer lattice Z³ do not have finite packing chromatic numbers.     

Partition into cliques for cubic graphs: Planar case, complexity and approximation

Given a graph G=(V,E) and a positive integer k, the partition into cliques (pic) decision problem consists of deciding whether there exists a partition of V into k disjoint subsets V₁,V₂,…,V_k such that the subgraph induced by each part V_i is a complete subgraph (clique) of G. In this paper, we establish both the NP-completeness of pic for planar cubic graphs and the Max SNP-hardness of pic for cubic graphs. We present a deterministic polynomial time -approximation algorithm for finding clique partitions in maximum degree three graphs.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Consecutive magic graphs

Let G be a graph of order n and size e. A vertex-magic total labeling is an assignment of the integers 1,2,…,n+e to the vertices and the edges of G, so that at each vertex, the vertex label and the labels on the edges incident at that vertex, add to a fixed constant, called the magic number of G. Such a labeling is a-vertex consecutive magic if the set of the labels of the vertices is {a+1,a+2,…,a+n}, and is b-edge consecutive magic if the set of labels of the edges is {b+1,b+2,…,b+e}. In this paper we prove that if an a-vertex consecutive magic graph has isolated vertices then the order and the size satisfy (n-1)²+n²=(2e+1)². Moreover, we show that every tree with even order is not a-vertex consecutive magic and, if a tree of odd order is a-vertex consecutive then a=n-1. Furthermore, we show that every a-vertex consecutive magic graph has minimum degree at least two if a=0, or both and 2a?e, and the minimum degree is at least three if both and 2a?e. Finally, we state analogous results for b-edge consecutive magic graphs.     

Nordhaus-Gaddum results for restrained domination and total restrained domination in graphs

Let G=(V,E) be a graph. A set S⊆V is a total restrained dominating set if every vertex is adjacent to a vertex in S and every vertex of V-S is adjacent to a vertex in V-S. A set S⊆V is a restrained dominating set if every vertex in V-S is adjacent to a vertex in S and to a vertex in V-S. The total restrained domination number of G (restrained domination number of G, respectively), denoted by γ_tr(G) (γ_r(G), respectively), is the smallest cardinality of a total restrained dominating set (restrained dominating set, respectively) of G. We bound the sum of the total restrained domination numbers of a graph and its complement, and provide characterizations of the extremal graphs achieving these bounds. It is known (see [G.S. Domke, J.H. Hattingh, S.T. Hedetniemi, R.C. Laskar, L.R. Markus, Restrained domination in graphs, Discrete Math. 203 (1999) 61-69.]) that if G is a graph of order n?2 such that both G and are not isomorphic to P₃, then . We also provide characterizations of the extremal graphs G of order n achieving these bounds.     

On the degrees of a strongly vertex-magic graph

Let G=(V,E) be a finite graph, where |V|=n?2 and |E|=e?1. A vertex-magic total labeling is a bijection λ from V∪E to the set of consecutive integers {1,2,…,n+e} with the property that for every v∈V, for some constant h. Such a labeling is strong if λ(V)={1,2,…,n}. In this paper, we prove first that the minimum degree of a strongly vertex-magic graph is at least two. Next, we show that if , then the minimum degree of a strongly vertex-magic graph is at least three. Further, we obtain upper and lower bounds of any vertex degree in terms of n and e. As a consequence we show that a strongly vertex-magic graph is maximally edge-connected and hamiltonian if the number of edges is large enough. Finally, we prove that semi-regular bipartite graphs are not strongly vertex-magic graphs, and we provide strongly vertex-magic total labeling of certain families of circulant graphs.