Constructing the nearly shortest path in crossed cubes

A graph G is panconnected if each pair of distinct vertices u,v∈V(G) are joined by a path of length l for all d_G(u,v)?l?|V(G)|-1, where d_G(u,v) is the length of a shortest path joining u and v in G. Recently, Fan et. al. [J. Fan, X. Lin, X. Jia, Optimal path embedding in crossed cubes, IEEE Trans. Parall. Distrib. Syst. 16 (2) (2005) 1190-1200, J. Fan, X. Jia, X. Lin, Complete path embeddings in crossed cubes, Inform. Sci. 176 (22) (2006) 3332-3346] and Xu et. al. [J.M. Xu, M.J. Ma, M. Lu, Paths in Möbius cubes and crossed cubes, Inform. Proc. Lett. 97 (3) (2006) 94-97] both proved that n-dimensional crossed cube, CQ_n, is almost panconnected except the path of length d_CQn(u,v)+1 for any two distinct vertices u,v∈V(CQ_n). In this paper, we give a necessary and sufficient condition to check for the existence of paths of length d_CQn(u,v)+1, called the nearly shortest paths, for any two distinct vertices u,v in CQ_n. Moreover, we observe that only some pair of vertices have no nearly shortest path and we give a construction scheme for the nearly shortest path if it exists.     

Pancyclicity of ternary n-cube networks under the conditional fault model

A graph G is said to be conditional k-edge-fault pancyclic if after removing k faulty edges from G, under the assumption that each vertex is incident to at least two fault-free edges, the resulting graph contains a cycle of every length from its girth to |V(G)|. In this paper, we consider ternary n-cube networks and show that they are conditional (4n−5)-edge-fault pancyclic.     

Fault-tolerant pancyclicity of augmented cubes

As an enhancement on the hypercube Qn, the augmented cube AQn, prosed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], not only retains some favorable properties of Qn but also possesses some embedding properties that Qn does not. For example, AQn is pancyclic, that is, AQn contains cycles of arbitrary length for n?2. This paper shows that AQn remains pancyclic provided faulty vertices and/or edges do not exceed 2n−3 and n?4.     

Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs

A bipartite graph G is bipancyclic if G has a cycle of length l for every even 4?l?|V(G)|. For a bipancyclic graph G and any edge e, G is edge-bipancyclic if e lies on a cycle of any even length l of G. In this paper, we show that the bubble-sort graph Bn is bipancyclic for n?4 and also show that it is edge-bipancyclic for n?5. Assume that F is a subset of E(Bn). We prove that Bn−F is bipancyclic, when n?4 and |F|?n−3. Since Bn is a (n−1)-regular graph, this result is optimal in the worst case.     

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 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)).     

Paths in Möbius cubes and crossed cubes

The Möbius cube MQn and the crossed cube CQn are two important variants of the hypercube Qn. This paper shows that for any two different vertices u and v in G∈{MQn,CQn} with n?3, there exists a uv-path of every length from dG(u,v)+2 to n²−1 except for a shortest uv-path, where dG(u,v) is the distance between u and v in G. This result improves some known results.     

Geodesic pancyclicity of twisted cubes

The hypercube is one of the most popular interconnection networks since it has simple structure and is easy to implement. An n-dimensional twisted cube, TQ_n, is an important variation of the hypercube Q_n and preserves many of its desirable properties. The problem of embedding linear arrays and cycles into a host graph has attracted substantial attention in recent years. The geodesic cycle embedding problem is for any two distinct vertices, to find all the possible lengths of cycles that include a shortest path joining them. In this paper, we prove that TQ_n is geodesic 2-pancyclic for each odd integer n ? 3. This result implies that TQ_n is edge-pancyclic for each odd integer n ? 3. Moreover, TQ_n × K₂ is also demonstrated to be geodesic 4-pancyclic.     

Upper signed k-domination in a general graph

Let k be a positive integer, and let G=(V,E) be a graph with minimum degree at least k−1. A function f:V→{−1,1} is said to be a signed k-dominating function (SkDF) if _∑u∈N[v]f(u)?k for every v∈V. An SkDF f of a graph G is minimal if there exists no SkDF g such that g≠f and g(v)?f(v) for every v∈V. The maximum of the values of _∑v∈Vf(v), taken over all minimal SkDFs f, is called the upper signed k-domination numberΓkS(G). In this paper, we present a sharp upper bound on this number for a general graph.     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.     

Consensus models: Computational complexity aspects in modern approaches to the list coloring problem

In the paper we study new approaches to the problem of list coloring of graphs. In the problem we are given a simple graph G=(V,E) and, for every v∈V, a nonempty set of integers S(v); we ask if there is a coloring c of G such that c(v)∈S(v) for every v∈V. Modern approaches, connected with applications, change the question—we now ask if S can be changed, using only some elementary transformations, to ensure that there is such a coloring and, if the answer is yes, what is the minimal number of changes. In the paper for studying the adding, the trading and the exchange models of list coloring, we use the following transformations:

•

adding of colors (the adding model): select two vertices u, v and a color c∈S(u); add c to S(v), i.e. set S(v):=S(v)∪{c};

•

trading of colors (the trading model): select two vertices u, v and a color c∈S(u); move c from S(u) to S(v), i.e. set S(u):=S(u)?{c} and S(v):=S(v)∪{c};

•

exchange of colors (the exchange model): select two vertices u, v and two colors c∈S(u), d∈S(v); exchange c with d, i.e. set S(u):=(S(u)?{c})∪{d} and S(v):=(S(v)?{d})∪{c}.

Our study focuses on computational complexity of the above models and their edge versions. We consider these problems on complete graphs, graphs with bounded cyclicity and partial k-trees, receiving in all cases polynomial algorithms or proofs of NP-hardness.     

On pancyclicity properties of OTIS-mesh

In optoelectronic OTIS multicomputer networks (also known as Swapped networks), electrical and optical interconnects are used for local and global communication, respectively. An interesting instance of the OTIS multicomputers is the OTIS-mesh. Pancyclicity is of great importance in the implementation of a variety of parallel algorithms in multicomputers. This paper addresses the Pancyclicity problem of OTIS-mesh. More precisely, we prove that if the factor graph G of an OTIS network is a 2-D or 3-D mesh with at least one even radix, OTIS-G can embed any cycle of length l, l∈{4,6,7,8,9,…,²|G|}.     

The edge-orientation problem and some of its variants on weighted graphs

Let G(V, E) be a connected undirected graph with n vertices and m edges, where each vertex v is associated with a cost C(v) and each edge e = (u, v) is associated with two weights, W(u → v) and W(v → u). The issue of assigning an orientation to each edge so that G becomes a directed graph is resolved in this paper. Determining a scheme to assign orientations of all edges such that max_x∈V{C(x)+∑_x→zW(x→z)} is minimized is the objective. This issue is called the edge-orientation problem (the EOP). Two variants of the EOP, the Out-Degree-EOP and the Vertex-Weighted EOP, are first proposed and then efficient algorithms for solving them on general graphs are designed. Ascertaining that the EOP is NP-hard on bipartite graphs and chordal graphs is the second result. Finally, an O(n log n)-time algorithm for the EOP on trees is designed. In general, the algorithmic results in this paper facilitate the implementation of the weighted fair queuing (WFQ) on real networks. The objective of the WFQ is to assign an effective weight for each flow to enhance link utilization. Our findings consequently can be easily extended to other classes of graphs, such as cactus graphs, block graphs, and interval graphs.     

Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the edges and the vertices. A total coloring is proper if no two adjacent or incident elements receive the same color. An adjacent vertex-distinguishing total coloring h of a simple graph G=(V,E) is a proper total coloring of G such that H(u)≠H(v) for any two adjacent vertices u and v, where H(u)={h(wu)|wu∈E(G)}∪{h(u)} and H(v)={h(xv)|xv∈E(G)}∪{h(v)}. The minimum number of colors required for an adjacent vertex-distinguishing edge coloring (resp. an adjacent vertex-distinguishing total coloring) of G is called the adjacent vertex-distinguishing edge chromatic number (resp. adjacent vertex-distinguishing total chromatic number) of G and denoted by (resp. χat(G)). In this paper, we consider the adjacent vertex-distinguishing edge chromatic number and adjacent vertex-distinguishing total chromatic number of the hypercube Qn, prove that for n?3 and χat(Qn)=Δ(Qn)+2 for n?2.     

Bipanconnectivity and edge-fault-tolerant bipancyclicity of hypercubes

A bipartite graph is bipancyclic if it contains a cycle of every even length from 4 to |V(G)| inclusive. It has been shown that Q_n is bipancyclic if and only if n?2. In this paper, we improve this result by showing that every edge of Q_n−E′ lies on a cycle of every even length from 4 to |V(G)| inclusive where E′ is a subset of E(Q_n) with |E′|?n−2. The result is proved to be optimal. To get this result, we also prove that there exists a path of length l joining any two different vertices x and y of Q_n when h(x,y)?l?|V(G)|−1 and l−h(x,y) is even where h(x,y) is the Hamming distance between x and y.     

Fault-tolerant cycle-embedding of crossed cubes

The crossed cube CQ_n introduced by Efe has many properties similar to those of the popular hypercube. However, the diameter of CQ_n is about one half of that of the hypercube. Failures of links and nodes in an interconnection network are inevitable. Hence, in this paper, we consider the hybrid fault-tolerant capability of the crossed cube. Letting f_e and f_v be the numbers of faulty edges and vertices in CQ_n, we show that a cycle of length l, for any 4?l?|V(CQ_n)|−f_v, can be embedded into a wounded crossed cube as long as the total number of faults (f_v+f_e) is no more than n−2, and we say that CQ_n is (n−2)-fault-tolerant pancyclic. This result is optimal in the sense that if there are n−1 faults, there is no guarantee of having a cycle of a certain length in it.     

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.     

A new sufficient condition for Hamiltonicity of graphs

Rahman and Kaykobad proved the following theorem on Hamiltonian paths in graphs. Let G be a connected graph with n vertices. If d(u)+d(v)+δ(u,v)?n+1 for each pair of distinct non-adjacent vertices u and v in G, where δ(u,v) is the length of a shortest path between u and v in G, then G has a Hamiltonian path. It is shown that except for two families of graphs a graph is Hamiltonian if it satisfies the condition in Rahman and Kaykobad's theorem. The result obtained in this note is also an answer for a question posed by Rahman and Kaykobad.     

Bandwidth on AT-free graphs

We study the classical Bandwidth problem from the viewpoint of parametrised algorithms. Given a graph G=(V,E) and a positive integer k, the Bandwidth problem asks whether there exists a bijective function β:{1,…,∣V∣}→V such that for every edge uv∈E, ∣β⁻¹(u)−β⁻¹(v)∣≤k. It is known that under standard complexity assumptions, no algorithm for Bandwidth with running time of the form f(k)n^O(1) exists, even when the input is restricted to trees. We initiate the search for classes of graphs where such algorithms do exist. We present an algorithm with running time n⋅2^O(klogk) for Bandwidth on AT-free graphs, a well-studied graph class that contains interval, permutation, and cocomparability graphs. Our result is the first non-trivial algorithm that shows fixed-parameter tractability of Bandwidth on a graph class on which the problem remains NP-complete.     

On identifying codes that are robust against edge changes

Assume that G = (V, E) is an undirected graph, and C ⊆ V. For every v ∈ V, denote I_r(G; v) = {u ∈ C: d(u,v) ≤ r}, where d(u,v) denotes the number of edges on any shortest path from u to v in G. If all the sets I_r(G; v) for v ∈ V are pairwise different, and none of them is the empty set, the code C is called r-identifying. The motivation for identifying codes comes, for instance, from finding faulty processors in multiprocessor systems or from location detection in emergency sensor networks. The underlying architecture is modelled by a graph. We study various types of identifying codes that are robust against six natural changes in the graph; known or unknown edge deletions, additions or both. Our focus is on the radius r = 1. We show that in the infinite square grid the optimal density of a 1-identifying code that is robust against one unknown edge deletion is 1/2 and the optimal density of a 1-identifying code that is robust against one unknown edge addition equals 3/4 in the infinite hexagonal mesh. Moreover, although it is shown that all six problems are in general different, we prove that in the binary hypercube there are cases where five of the six problems coincide.