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.     

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 a conjecture concerning the orientation number of a graph

For a connected graph G containing no bridges, let D(G) be the family of strong orientations of G; and for any D∈D(G), we denote by d(D) the diameter of D. The orientation number of G is defined by . Let G(p,q;m) denote the family of simple graphs obtained from the disjoint union of two complete graphs K_p and K_q by adding m edges linking them in an arbitrary manner. The study of the orientation numbers of graphs in G(p,q;m) was introduced by Koh and Ng [K.M. Koh, K.L. Ng, The orientation number of two complete graphs with linkages, Discrete Math. 295 (2005) 91-106]. Define and . In this paper we prove a conjecture on α proposed by K.M. Koh and K.L. Ng in the above mentioned paper, for q≥p+4.     

Injective colorings of sparse graphs

Let denote the maximum average degree (over all subgraphs) of G and let χ_i(G) denote the injective chromatic number of G. We prove that if , then χ_i(G)≤Δ(G)+1; and if , then χ_i(G)=Δ(G). Suppose that G is a planar graph with girth g(G) and Δ(G)≥4. We prove that if g(G)≥9, then χ_i(G)≤Δ(G)+1; similarly, if g(G)≥13, then χ_i(G)=Δ(G).     

Boxicity of line graphs

The boxicity of a graph H, denoted by , is the minimum integer k such that H is an intersection graph of axis-parallel k-dimensional boxes in R^k. In this paper we show that for a line graph G of a multigraph, , where Δ(G) denotes the maximum degree of G. Since G is a line graph, Δ(G)≤2(χ(G)−1), where χ(G) denotes the chromatic number of G, and therefore, . For the d-dimensional hypercube Q_d, we prove that . The question of finding a nontrivial lower bound for was left open by Chandran and Sivadasan in [L. Sunil Chandran, Naveen Sivadasan, The cubicity of Hypercube Graphs. Discrete Mathematics 308 (23) (2008) 5795–5800].The above results are consequences of bounds that we obtain for the boxicity of a fully subdivided graph (a graph that can be obtained by subdividing every edge of a graph exactly once).     

Colouring games on outerplanar graphs and trees

Let f be a graph function which assigns to each graph H a non-negative integer f(H)≤|V(H)|. The f-game chromatic number of a graph G is defined through a two-person game. Let X be a set of colours. Two players, Alice and Bob, take turns colouring the vertices of G with colours from X. A partial colouring c of G is legal (with respect to graph function f) if for any subgraph H of G, the sum of the number of colours used in H and the number of uncoloured vertices of H is at least f(H). Both Alice and Bob must colour legally (i.e., the partial colouring produced needs to be legal). The game ends if either all the vertices are coloured or there are uncoloured vertices with no legal colour. In the former case, Alice wins the game. In the latter case, Bob wins the game. The f-game chromatic number of G, χ_g(f,G), is the least number of colours that the colour set X needs to contain so that Alice has a winning strategy. Let be the graph function defined as , for any n≥3 and otherwise. Then is called the acyclic game chromatic number of G. In this paper, we prove that any outerplanar graph G has acyclic game chromatic number at most 7. For any integer k, let ?_k be the graph function defined as ?_k(K₂)=2 and ?_k(P_k)=3 (P_k is the path on k vertices) and ?_k(H)=0 otherwise. This paper proves that if k≥8 then for any tree T, χ_g(?_k,T)≤9. On the other hand, if k≤6, then for any integer n, there is a tree T such that χ_g(?_k,T)≥n.     

Distance irredundance and connected domination numbers of a graph

Let k be a positive integer and G be a connected graph. This paper considers the relations among four graph theoretical parameters: the k-domination number γ_k(G), the connected k-domination number ; the k-independent domination number and the k-irredundance number ir_k(G). The authors prove that if an ir_k-set X is a k-independent set of G, then , and that for k?2, if ir_k(G)=1, if ir_k(G) is odd, and if ir_k(G) is even, which generalize some known results.     

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 .     

A note on edge-graceful spectra of the square of paths

For a simple path P_r on r vertices, the square of P_r is the graph on the same set of vertices of P_r, and where every pair of vertices of distance two or less in P_r is connected by an edge. Given a (p,q)-graph G with p vertices and q edges, and a nonnegative integer k, G is said to be k-edge-graceful if the edges can be labeled bijectively by k,k+1,…,k+q−1, so that the induced vertex sums are pairwise distinct, where the vertex sum at a vertex is the sum of the labels of all edges incident to such a vertex, modulo the number of vertices p. We call the set of all such k the edge-graceful spectrum of G, and denote it by egI(G). In this article, the edge-graceful spectrum for the square of paths is completely determined for odd r.     

Total colorings and list total colorings of planar graphs without intersecting 4-cycles

Suppose that G is a planar graph with maximum degree Δ and without intersecting 4-cycles, that is, no two cycles of length 4 have a common vertex. Let χ^″(G), and denote the total chromatic number, list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that χ^″(G)=Δ+1 if Δ≥7, and and if Δ(G)≥8. Furthermore, if G is a graph embedded in a surface of nonnegative characteristic, then our results also hold.     

Posets of annular non-crossing partitions of types B and D

We study the set of annular non-crossing permutations of type B, and we introduce a corresponding set of annular non-crossing partitions of type B, where p and q are two positive integers. We prove that the natural bijection between and is a poset isomorphism, where the partial order on is induced from the hyperoctahedral group B_p+q, while is partially ordered by reverse refinement. In the case when q=1, we prove that is a lattice with respect to reverse refinement order.We point out that an analogous development can be pursued in type D, where one gets a canonical isomorphism between and . For q=1, the poset coincides with a poset “NC^(D)(p+1)” constructed in a paper by Athanasiadis and Reiner [C.A. Athanasiadis, V. Reiner, Noncrossing partitions for the group D_n, SIAM Journal of Discrete Mathematics 18 (2004) 397-417], and is a lattice by the results of that paper.     

Directed 3-cycle decompositions of complete directed graphs with quadratic leaves

Let G be a vertex-disjoint union of directed cycles in the complete directed graph D_t, let |E(G)| be the number of directed edges of G and suppose or if t=5, and if t=6. It is proved in this paper that for each positive integer t, there exist -decompositions for D_t−G if and only if .     

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.     

Vertex-transitive self-complementary uniform hypergraphs of prime order

For an integer n and a prime p, let . In this paper, we present a construction for vertex-transitive self-complementary k-uniform hypergraphs of order n for each integer n such that for every prime p, where ?=max{k₍₂₎,(k−1)₍₂₎}, and consequently we prove that the necessary conditions on the order of vertex-transitive self-complementary uniform hypergraphs of rank k=2^? or k=2^?+1 due to Potoňick and Šajna are sufficient. In addition, we use Burnside’s characterization of transitive groups of prime degree to characterize the structure of vertex-transitive self-complementary k-hypergraphs which have prime order p in the case where k=2^? or k=2^?+1 and , and we present an algorithm to generate all of these structures. We obtain a bound on the number of distinct vertex-transitive self-complementary graphs of prime order , up to isomorphism.     

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.     

Chromatic capacity and graph operations

The chromatic capacityχ_cap(G) of a graph G is the largest k for which there exists a k-coloring of the edges of G such that, for every coloring of the vertices of G with the same colors, some edge is colored the same as both its vertices. We prove that there is an unbounded function f:N→N such that χ_cap(G)?f(χ(G)) for almost every graph G, where χ denotes the chromatic number. We show that for any positive integers n and k with k?n/2 there exists a graph G with χ(G)=n and χ_cap(G)=n-k, extending a result of Greene. We obtain bounds on that are tight as r→∞, where is the complete n-partite graph with r vertices in each part. Finally, for any positive integers p and q we construct a graph G with χ_cap(G)+1=χ(G)=p that contains no odd cycles of length less than q.     

Edge colouring by total labellings

We introduce the concept of an edge-colouring total k-labelling. This is a labelling of the vertices and the edges of a graph G with labels 1,2,…,k such that the weights of the edges define a proper edge colouring of G. Here the weight of an edge is the sum of its label and the labels of its two endvertices. We define to be the smallest integer k for which G has an edge-colouring total k-labelling. This parameter has natural upper and lower bounds in terms of the maximum degree Δ of . We improve the upper bound by 1 for every graph and prove . Moreover, we investigate some special classes of graphs.     

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

     

Roman domination in regular graphs

A Roman domination function on a graph G=(V(G),E(G)) is a function f:V(G)→{0,1,2} satisfying the condition that every vertex u for which f(u)=0 is adjacent to at least one vertex v for which f(v)=2. The weight of a Roman dominating function is the value f(V(G))=∑_u∈V(G)f(u). The minimum weight of a Roman dominating function on a graph G is called the Roman domination number of G. Cockayne et al. [E. J. Cockayne et al. Roman domination in graphs, Discrete Mathematics 278 (2004) 11-22] showed that γ(G)≤γ_R(G)≤2γ(G) and defined a graph G to be Roman if γ_R(G)=2γ(G). In this article, the authors gave several classes of Roman graphs: P_3k,P_3k+2,C_3k,C_3k+2 for k≥1, K_m,n for min{m,n}≠2, and any graph G with γ(G)=1; In this paper, we research on regular Roman graphs and prove that: (1) the circulant graphs and , n⁄≡1 (mod (2k+1)), (n≠2k) are Roman graphs, (2) the generalized Petersen graphs P(n,2k+1)( (mod 4) and ), P(n,1) (n⁄≡2 (mod 4)), P(n,3) ( (mod 4)) and P(11,3) are Roman graphs, and (3) the Cartesian product graphs are Roman graphs.     

Adjoint polynomials of bridge–path and bridge–cycle graphs and Chebyshev polynomials

The chromatic polynomial of a simple graph G with n>0 vertices is a polynomial of degree n, where α_k(G) is the number of k-independent partitions of G for all k. The adjoint polynomial of G is defined to be , where is the complement of G. We find explicit formulas for the adjoint polynomials of the bridge–path and bridge–cycle graphs. Consequence, we find the zeros of the adjoint polynomials of several families of graphs.