Cubicity, boxicity, and vertex cover

A k-dimensional box is the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line. The boxicity of a graph G, denoted as box(G), is the minimum integer k such that G is the intersection graph of a collection of k-dimensional boxes. A unit cube in k-dimensional space or a k-cube is defined as the cartesian product R₁×R₂×?×R_k where each R_i is a closed interval on the real line of the form [a_i,a_i+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. In this paper we show that cub(G)≤t+⌈log(n−t)⌉−1 and , where t is the cardinality of a minimum vertex cover of G and n is the number of vertices of G. We also show the tightness of these upper bounds.F.S. Roberts in his pioneering paper on boxicity and cubicity had shown that for a graph G, and , where n is the number of vertices of G, and these bounds are tight. We show that if G is a bipartite graph then and this bound is tight. We also show that if G is a bipartite graph then . We point out that there exist graphs of very high boxicity but with very low chromatic number. For example there exist bipartite (i.e., 2 colorable) graphs with boxicity equal to . Interestingly, if boxicity is very close to , then chromatic number also has to be very high. In particular, we show that if , s≥0, then , where χ(G) is the chromatic number of G.     

On the circumference of a graph and its complement

Let G be a graph of order n and circumference c(G). Let be the complement of G. We prove that and show sharpness of this bound.     

Ore-type conditions implying 2-factors consisting of short cycles

For every graph G, let . The main result of the paper says that every n-vertex graph G with contains each spanning subgraph H all whose components are isomorphic to graphs in . This generalizes the earlier results of Justesen, Enomoto, and Wang, and is a step towards an Ore-type analogue of the Bollobás-Eldridge-Catlin Conjecture.     

Game colouring of the square of graphs

This paper studies the game chromatic number and game colouring number of the square of graphs. In particular, we prove that if G is a forest of maximum degree Δ≥9, then , and there are forests G with . It is also proved that for an outerplanar graph G of maximum degree Δ, , and for a planar graph G of maximum degree Δ, .     

Disjoint hamiltonian cycles in bipartite graphs

Let G=(X,Y) be a bipartite graph and define . Moon and Moser [J. Moon, L. Moser, On Hamiltonian bipartite graphs, Israel J. Math. 1 (1963) 163-165. MR 28 # 4540] showed that if G is a bipartite graph on 2n vertices such that , then G is hamiltonian, sharpening a classical result of Ore [O. Ore, A note on Hamilton circuits, Amer. Math. Monthly 67 (1960) 55] for bipartite graphs. Here we prove that if G is a bipartite graph on 2n vertices such that , then G contains k edge-disjoint hamiltonian cycles. This extends the result of Moon and Moser and a result of R. Faudree et al. [R. Faudree, C. Rousseau, R. Schelp, Edge-disjoint Hamiltonian cycles, Graph Theory Appl. Algorithms Comput. Sci. (1984) 231-249].     

On signed cycle domination in graphs

Let G=(V,E) be a graph, a function f:E→{−1,1} is said to be an signed cycle dominating function (SCDF) of G if ∑_e∈E(C)f(e)≥1 holds for any induced cycle C of G. The signed cycle domination number of G is defined as is an SCDF of G}. In this paper, we obtain bounds on , characterize all connected graphs G with , and determine the exact value of for some special classes of graphs G. In addition, we pose some open problems and conjectures.     

Some relations between rank, chromatic number and energy of graphs

The energy of a graph G, denoted by E(G), is defined as the sum of the absolute values of all eigenvalues of G. Let G be a graph of order n and be the rank of the adjacency matrix of G. In this paper we characterize all graphs with . Among other results we show that apart from a few families of graphs, , where n is the number of vertices of G, and χ(G) are the complement and the chromatic number of G, respectively. Moreover some new lower bounds for E(G) in terms of are given.     

On the signed edge domination number of graphs

Let be the signed edge domination number of G. In 2006, Xu conjectured that: for any 2-connected graph G of order n(n≥2), . In this article we show that this conjecture is not true. More precisely, we show that for any positive integer m, there exists an m-connected graph G such that . Also for every two natural numbers m and n, we determine , where K_m,n is the complete bipartite graph with part sizes m and n.     

Generalization of transitive fraternal augmentations for directed graphs and its applications

Let be a directed graph. A transitive fraternal augmentation of is a directed graph with the same vertex set, including all the arcs of and such that for any vertices x,y,z,

1.

if and then or (fraternity);

2.

if and then (transitivity).

In this paper, we explore some generalization of the transitive fraternal augmentations for directed graphs and its applications. In particular, we show that the 2-coloring number col₂(G)≤O(∇₁(G)∇₀(G)²), where ∇_k(G) (k≥0) denotes the greatest reduced average density with depth k of a graph G; we give a constructive proof that ∇_k(G) bounds the distance (k+1)-coloring number col_k+1(G) with a function f(∇_k(G)). On the other hand, ∇_k(G)≤(col_2k+1(G))^2k+1. We also show that an inductive generalization of transitive fraternal augmentations can be used to study nonrepetitive colorings of graphs.     

Domination of generalized Cartesian products

The generalized prism πG of G is the graph consisting of two copies of G, with edges between the copies determined by a permutation π acting on the vertices of G. We define a generalized Cartesian product that corresponds to the Cartesian product when π is the identity, and the generalized prism when H is the graph K₂. Burger, Mynhardt and Weakley [A.P. Burger, C.M. Mynhardt, W.D. Weakley, On the domination number of prisms of graphs, Discuss. Math. Graph Theory 24 (2) (2004) 303-318.] characterized universal doublers, i.e. graphs for which γ(πG)=2γ(G) for any π. In general for any n≥2 and permutation π, and a graph attaining equality in this upper bound for all π is called a universal multiplier. We characterize such graphs.     

On edge domination numbers of graphs

Let and be the signed edge domination number and signed star domination number of G, respectively. We prove that holds for all graphs G without isolated vertices, where n=|V(G)|?4 and m=|E(G)|, and pose some problems and conjectures.     

Total restrained domination in trees

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. The total restrained domination number of G, denoted by γ_tr(G), is the smallest cardinality of a total restrained dominating set of G. We show that if T is a tree of order n, then . Moreover, we show that if T is a tree of order , then . We then constructively characterize the extremal trees T of order n achieving these lower bounds.     

A note on an embedding problem in transitive tournaments

Let TT_n be a transitive tournament on n vertices. It is known Görlich, Pil?niak, Wo?niak, (2006) [3] that for any acyclic oriented graph of order n and size not greater than , two graphs isomorphic to are arc-disjoint subgraphs of TT_n. In this paper, we consider the problem of embedding of acyclic oriented graphs into their complements in transitive tournaments. We show that any acyclic oriented graph of size at most is embeddable into all its complements in TT_n. Moreover, this bound is generally the best possible.     

Inverse degree and edge-connectivity

Let G be a connected graph with vertex set V(G), order n=|V(G)|, minimum degree δ and edge-connectivity λ. Define the inverse degree of G as , where d(v) denotes the degree of the vertex v. We show that if

     

General neighbour-distinguishing index via chromatic number

An edge colouring of a graph G without isolated edges is neighbour-distinguishing if any two adjacent vertices have distinct sets consisting of colours of their incident edges. The general neighbour-distinguishing index of G is the minimum number of colours in a neighbour-distinguishing edge colouring of G. Gy?ri et al. [E. Gy?ri, M. Horňák, C. Palmer, M. Wo?niak, General neighbour-distinguishing index of a graph, Discrete Math. 308 (2008) 827-831] proved that provided G is bipartite and gave a complete characterisation of bipartite graphs according to their general neighbour-distinguishing index. The aim of this paper is to prove that if χ(G)≥3, then . Therefore, if log₂χ(G)∉Z, then .     

Edges not contained in triangles and the number of contractible edges in a 4-connected graph

Let G be a 4-connected graph, and let E_c(G) denote the set of 4-contractible edges of G and let denote the set of those edges of G which are not contained in a triangle. Under this notation, we show that if , then we have .     

On the Laplacian spectral radii of trees

Let Δ(T) and μ(T) denote the maximum degree and the Laplacian spectral radius of a tree T, respectively. Let T_n be the set of trees on n vertices, and . In this paper, we determine the two trees which take the first two largest values of μ(T) of the trees T in when . And among the trees in , the tree which alone minimizes the Laplacian spectral radius is characterized. We also prove that for two trees T₁ and T₂ in , if Δ(T₁)>Δ(T₂) and , then μ(T₁)>μ(T₂). As an application of these results, we give a general approach about extending the known ordering of trees in T_n by their Laplacian spectral radii.     

An upper bound on the paired-domination number in terms of the number of edges in the graph

In this paper, we continue the study of paired domination in graphs introduced by Haynes and Slater [T.W. Haynes, P.J. Slater, Paired-domination in graphs, Networks 32 (1998) 199-206]. A paired-dominating set of a graph is a dominating set whose induced subgraph contains a perfect matching. The paired-domination number of a graph G, denoted by , is the minimum cardinality of a paired-dominating set in G. We show that if G is a connected graph of size m≥18 with minimum degree at least 2, then and we characterize the (infinite family of) graphs that achieve equality in this bound.     

The asymptotic number of spanning trees in circulant graphs

Let T(G) be the number of spanning trees in graph G. In this note, we explore the asymptotics of T(G) when G is a circulant graph with given jumps.The circulant graph is the 2k-regular graph with n vertices labeled 0,1,2,…,n−1, where node i has the 2k neighbors i±s₁,i±s₂,…,i±s_k where all the operations are . We give a closed formula for the asymptotic limit as a function of s₁,s₂,…,s_k. We then extend this by permitting some of the jumps to be linear functions of n, i.e., letting s_i, d_i and e_i be arbitrary integers, and examining

     

On the ratios between packing and domination parameters of a graph

The relationship ρ_L(G)≤ρ(G)≤γ(G) between the lower packing number ρ_L(G), the packing number ρ(G) and the domination number γ(G) of a graph G is well known. In this paper we establish best possible bounds on the ratios of the packing numbers of any (connected) graph to its six domination-related parameters (the lower and upper irredundance numbers ir and IR, the lower and upper independence numbers i and β, and the lower and upper domination numbers γ and Γ). In particular, best possible constants a_θ, b_θ, c_θ and d_θ are found for which the inequalities and hold for any connected graph G and all θ∈{ir,γ,i,β,Γ,IR}. From our work it follows, for example, that and for any connected graph G, and that these inequalities are best possible.