On the k-tuple domination of de Bruijn and Kautz digraphs

In a digraph G, a vertex u is said to dominate itself and vertices v such that (u,v) is an arc of G. For a positive integer k, a k-tuple dominating set D of a digraph is a subset of vertices such that every vertex is dominated by at least k vertices in D. The k-tuple domination number of a given digraph is the minimum cardinality of a k-tuple dominating set of the digraph. In this letter, we give the exact values of the k-tuple domination number of de Bruijn and Kautz digraphs.     

The twin domination number in generalized de Bruijn digraphs

Let G=(V,A) be a digraph. A set T of vertices of G is a twin dominating set of G if for every vertex v∈V?T, there exist u,w∈T (possibly u=w) such that arcs (u,v),(v,w)∈A. The twin domination numberγ^∗(G) of G is the cardinality of a minimum twin dominating set of G. In this paper we investigate the twin domination number in generalized de Bruijn digraphs GB(n,d). For the digraphs GB(n,d), we first establish sharp bounds on the twin domination number. Secondly, we give the exact values of the twin domination number for several types of GB(n,d) by constructing minimum twin dominating sets in the digraphs. Finally, we present sharp upper bounds for some special generalized de Bruijn digraphs.     

On Clark and Suen bound-type results for k-domination and Roman domination of Cartesian product graphs

A set S of vertices of a graph G is a dominating set for G if every vertex of G is adjacent to at least one vertex of S. The domination number γ(G), of G, is the minimum cardinality of a dominating set in G. Moreover, if the maximum degree of G is Δ, then for every positive integer k≤Δ, the set S is a k-dominating set in G if every vertex outside of S is adjacent to at least k vertices of S. The k-domination number of G, denoted by γ _k (G), is the minimum cardinality of a k-dominating set in G. A map f: V→<texlscub>0, 1, 2</texlscub>is a Roman dominating function for G if for every vertex v with f(v)=0, there exists a vertex u∈N(v) such that f(u)=2. The weight of a Roman dominating function is f(V)=∑ _u∈V f(u). The Roman domination number γ_R(G), of G, is the minimum weight of a Roman dominating function on G. In this paper, we obtain that for any two graphs G and H, the k-domination number of the Cartesian product of G and H is bounded below by γ(G)γ _k (H)/2. Also, we obtain that the domination number of Cartesian product of G and H is bounded below by γ(G)γ_R(H)/3.     

k-tuple domination in graphs

In a graph G, a vertex is said to dominate itself and all of its neighbors. For a fixed positive integer k, the k-tuple domination problem is to find a minimum sized vertex subset in a graph such that every vertex in the graph is dominated by at least k vertices in this set. The current paper studies k-tuple domination in graphs from an algorithmic point of view. In particular, we give a linear-time algorithm for the k-tuple domination problem in strongly chordal graphs, which is a subclass of chordal graphs and includes trees, block graphs, interval graphs and directed path graphs. We also prove that the k-tuple domination problem is NP-complete for split graphs (a subclass of chordal graphs) and for bipartite graphs.     

A Broadcasting Protocol in Line Digraphs

We propose broadcasting algorithms for line digraphs in the telegraph model. The new protocols use a broadcasting protocol for a graph G to obtain a broadcasting protocol for the graph L^kG, the graph obtained by applying k times, the line digraph operation to G. As a consequence improved bounds for the broadcasting time in De Bruijn, Kautz, and Wrapped Butterfly digraphs are obtained.     

On the oriented chromatic number of grids

In this paper, we focus on the oriented coloring of graphs. Oriented coloring is a coloring of the vertices of an oriented graph G without symmetric arcs such that (i) no two neighbors in G are assigned the same color, and (ii) if two vertices u and v such that (u,v)∈A(G) are assigned colors c(u) and c(v), then for any (z,t)∈A(G), we cannot have simultaneously c(z)=c(v) and c(t)=c(u). The oriented chromatic number of an unoriented graph G is the smallest number k of colors for which any of the orientations of G can be colored with k colors.The main results we obtain in this paper are bounds on the oriented chromatic number of particular families of planar graphs, namely 2-dimensional grids, fat trees and fat fat trees.     

Minimum feedback vertex sets in shuffle-based interconnection networks

Given a graph G, the problem is to construct a smallest subset S of vertices whose deletion results in an acyclic subgraph. The set S is called a minimum feedback vertex set for G.Tight upper and lower bounds on the cardinality of minimum feedback vertex sets have been previously obtained for some hypercube-like networks, such as meshes, tori, butterflies, cube-connected cycles and hypercubes. In this paper we construct minimum feedback vertex sets and determine their cardinalities in certain shuffle-based interconnection networks, such as shuffle-exchange, de Bruijn and Kautz networks.     

A Fan-type result on k-ordered graphs

For a positive integer k, a graph G is k-ordered hamiltonian if for every ordered sequence of k vertices there is a hamiltonian cycle that encounters the vertices of the sequence in the given order. In this paper, we show that if G is a ⌊3k/2⌋-connected graph of order n?100k, and d(u)+d(v)?n for any two vertices u and v with d(u,v)=2, then G is k-ordered hamiltonian. Our result implies the theorem of G. Chen et al. [Ars Combin. 70 (2004) 245-255] [1], which requires the degree sum condition for all pairs of non-adjacent vertices, not just those distance 2 apart.     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

Bounds for the 2-domination number of toroidal grid graphs

A k-dominating set for a graph G(V, E) is a set of vertices D? V such that every vertex v∈V\ D is adjacent to at least k vertices in D. The k-domination number of G, denoted by γ _k (G), is the cardinality of a smallest k-dominating set of G. Here we establish lower and upper bounds of γ _k (C _m ×C _n ) for k=2. In some cases, these bounds agree so that the exact 2-domination number is obtained.     

Lucky labelings of graphs

Suppose the vertices of a graph G were labeled arbitrarily by positive integers, and let S(v) denote the sum of labels over all neighbors of vertex v. A labeling is lucky if the function S is a proper coloring of G, that is, if we have S(u)≠S(v) whenever u and v are adjacent. The least integer k for which a graph G has a lucky labeling from the set {1,2,…,k} is the lucky number of G, denoted by η(G).Using algebraic methods we prove that η(G)?k+1 for every bipartite graph G whose edges can be oriented so that the maximum out-degree of a vertex is at most k. In particular, we get that η(T)?2 for every tree T, and η(G)?3 for every bipartite planar graph G. By another technique we get a bound for the lucky number in terms of the acyclic chromatic number. This gives in particular that for every planar graph G. Nevertheless we offer a provocative conjecture that η(G)?χ(G) for every graph G.     

The super-connected property of recursive circulant graphs

In a graph G, a k-container C_k(u,v) is a set of k disjoint paths joining u and v. A k-container C_k(u,v) is k∗-container if every vertex of G is passed by some path in C_k(u,v). A graph G is k∗-connected if there exists a k∗-container between any two vertices. An m-regular graph G is super-connected if G is k∗-connected for any k with 1?k?m. In this paper, we prove that the recursive circulant graphs G(2^m,4), proposed by Park and Chwa [Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m≠2.     

Hamiltonian paths and cycles with prescribed edges in the 3-ary n-cube

The k-ary n-cube has been one of the most popular interconnection networks for massively parallel systems. Given a set P of at most 2n − 2 (n ? 2) prescribed edges and two vertices u and v, we show that the 3-ary n-cube contains a Hamiltonian path between u and v passing through all edges of P if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths, none of them having u or v as internal vertices or both of them as end-vertices. As an immediate result, the 3-ary n-cube contains a Hamiltonian cycle passing through a set P of at most 2n − 1 prescribed edges if and only if the subgraph induced by P consists of pairwise vertex-disjoint paths.     

The super laceability of the hypercubes

A k-containerC(u,v) of a graph G is a set of k disjoint paths joining u to v. A k-container C(u,v) is a k∗-container if every vertex of G is incident with a path in C(u,v). A bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u, v from different partite set of G. A bipartite graph G with connectivity k is super laceable if it is i∗-laceable for all i?k. A bipartite graph G with connectivity k is f-edge fault-tolerant super laceable if G−F is i∗-laceable for any 1?i?k−f and for any edge subset F with |F|=f<k−1. In this paper, we prove that the hypercube graph Q_r is super laceable. Moreover, Q_r is f-edge fault-tolerant super laceable for any f?r−2.     

Total restrained domination in graphs

In this paper, we initiate the study of a variation of standard domination, namely total restrained domination. Let G=(V,E) be a graph. A set D⊆V is a total restrained dominating set if every vertex in V−D has at least one neighbor in D and at least one neighbor in V−D, and every vertex in D has at least one neighbor in D. The total restrained domination number of G, denoted by γ_tr(G), is the minimum cardinality of all total restrained dominating sets of G. We determine the best possible upper and lower bounds for γ_tr(G), characterize those graphs achieving these bounds and find the best possible lower bounds for where both G and are connected.     

Isomorphic factorization, the Kronecker product and the line digraph

In this paper, we investigate isomorphic factorizations of the Kronecker product graphs. Using these relations, it is shown that (1) the Kronecker product of the d-out-regular digraph and the complete symmetric digraph is factorized into the line digraph, (2) the Kronecker product of the Kautz digraph and the de Bruijn digraph is factorized into the Kautz digraph, (3) the Kronecker product of binary generalized de Bruijn digraphs is factorized into the binary generalized de Bruijn digraph.     

Constructing Labeling Schemes through Universal Matrices

Let f be a function on pairs of vertices. An f -labeling scheme for a family of graphs ℱ labels the vertices of all graphs in ℱ such that for every graph G∈ℱ and every two vertices u,v∈G, f(u,v) can be inferred by merely inspecting the labels of u and v. The size of a labeling scheme is the maximum number of bits used in a label of any vertex in any graph in ℱ. This paper illustrates that the notion of universal matrices can be used to efficiently construct f-labeling schemes.     

Two algorithms for minimum 2-connected r-hop dominating set

For a graph G=(V,E), a subset D⊆V is an r-hop dominating set if every vertex u∈V−D is at most r-hops away from D. It is a 2-connected r-hop dominating set if the subgraph of G induced by D is 2-connected. In this paper, we present two approximation algorithms to compute minimum 2-connected r-hop dominating set. The first one is a greedy algorithm using ear decomposition of 2-connected graphs. This algorithm is applicable to any 2-connected general graph. The second one is a three-phase algorithm which is only applicable to unit disk graphs. For both algorithms, performance ratios are given.     

On the locatic number of graphs

A vertex v of a connected graph G distinguishes a pair u, w of vertices of G if d(v, u)≠d(v, w), where d(·,·) denotes the length of a shortest path between two vertices in G. A k-partition Π={S ₁, S ₂, …, S _k } of the vertex set of G is said to be a locatic partition if for every pair of distinct vertices v and w of G, there exists a vertex s∈S _i for all 1≤i≤k that distinguishes v and w. The cardinality of a largest locatic partition is called the locatic number of G. In this paper, we study the locatic number of paths, cycles and characterize all the connected graphs of order n having locatic number n, n?1 and n?2. Some realizable results are also given in this paper.     

On edge connectivity of direct products of graphs

Let λ(G) be the edge connectivity of G. The direct product of graphs G and H is the graph with vertex set V(G×H)=V(G)×V(H), where two vertices (u₁,v₁) and (u₂,v₂) are adjacent in G×H if u₁u₂∈E(G) and v₁v₂∈E(H). We prove that λ(G×Kn)=min{n(n−1)λ(G),(n−1)δ(G)} for every nontrivial graph G and n?3. We also prove that for almost every pair of graphs G and H with n vertices and edge probability p, G×H is k-connected, where k=O(²(n/logn)).