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.     

The super connectivity of augmented cubes

The augmented cube AQn, proposed by Choudum and Sunitha [S.A. Choudum, V. Sunitha, Augmented cubes, Networks 40 (2) (2002) 71-84], is a (2n−1)-regular (2n−1)-connected graph (n≠3). This paper determines that the super connectivity of AQn is 4n−8 for n?6 and the super edge-connectivity is 4n−4 for n?5. That is, for n?6 (respectively, n?5), at least 4n−8 vertices (respectively, 4n−4 edges) of AQn are removed to get a disconnected graph that contains no isolated vertices. When the augmented cube is used to model the topological structure of a large-scale parallel processing system, these results can provide more accurate measurements for reliability and fault tolerance of the system.     

Conditional fault hamiltonian connectivity of the complete graph

A path in G is a hamiltonian path if it contains all vertices of G. A graph G is hamiltonian connected if there exists a hamiltonian path between any two distinct vertices of G. The degree of a vertex u in G is the number of vertices of G adjacent to u. We denote by δ(G) the minimum degree of vertices of G. A graph G is conditional k edge-fault tolerant hamiltonian connected if G−F is hamiltonian connected for every F⊂E(G) with |F|?k and δ(G−F)?3. The conditional edge-fault tolerant hamiltonian connectivity is defined as the maximum integer k such that G is k edge-fault tolerant conditional hamiltonian connected if G is hamiltonian connected and is undefined otherwise. Let n?4. We use Kn to denote the complete graph with n vertices. In this paper, we show that for n∉{4,5,8,10}, , , , and .     

Ranking numbers of graphs

Given a graph G, a vertex ranking (or simply, ranking) of G is a mapping f from V(G) to the set of all positive integers, such that for any path between two distinct vertices u and v with f(u)=f(v), there is a vertex w in the path with f(w)>f(u). If f is a ranking of G, the ranking number of G under f, denoted γf(G), is defined by , and the ranking number of G, denoted γ(G), is defined by . The vertex ranking problem is to determine the ranking number γ(G) of a given graph G. This problem is a natural model for the manufacturing scheduling problem. We study the ranking numbers of graphs in this paper. We consider the relation between the ranking numbers and the minimal cut sets, and the relation between the ranking numbers and the independent sets. From this, we obtain the ranking numbers of the powers of paths and the powers of cycles, the Cartesian product of P₂ with Pn or Cn, and the caterpilars. And we also find the vertex ranking numbers of the composition of two graphs in this paper.     

Augmented k-ary n-cubes

We define an interconnection network AQ_n,k which we call the augmented k-ary n-cube by extending a k-ary n-cube in a manner analogous to the existing extension of an n-dimensional hypercube to an n-dimensional augmented cube. We prove that the augmented k-ary n-cube AQ_n,k has a number of attractive properties (in the context of parallel computing). For example, we show that the augmented k-ary n-cube AQ_n,k: is a Cayley graph, and so is vertex-symmetric, but not edge-symmetric unless n = 2; has connectivity 4n − 2 and wide-diameter at most max{(n − 1)k − (n − 2), k + 7}; has diameter , when n = 2; and has diameter at most , for n ? 3 and k even, and at most , for n ? 3 and k odd.     

Acyclic chromatic index of planar graphs with triangles

A proper edge coloring of a graph G is called acyclic if there is no 2-colored cycle in G. The acyclic chromatic index of G, denoted by , is the least number of colors in an acyclic edge coloring of G. Let G be a planar graph with maximum degree Δ(G). In this paper, we show that , if G contains no 4-cycle; , if G contains no intersecting triangles; and if G contains no adjacent triangles.     

On edge covering colorings of graphs

An edge covering coloring of a graph G is an edge-coloring of G such that each color appears at each vertex at least one time. The maximum integer k such that G has an edge covering coloring with k colors is called the edge covering chromatic index of G and denoted by . It is known that for any graph G with minimum degree δ(G), it holds that . Based on the subgraph of G induced by the vertices of minimum degree, we find a new sufficient condition for a graph G to satisfy . This result substantially extends a result of Wang et al. in 2006.     

Flow equivalent trees in undirected node-edge-capacitated planar graphs

Given an edge-capacitated undirected graph G=(V,E,C) with edge capacity , n=|V|, an s−t edge cut C of G is a minimal subset of edges whose removal from G will separate s from t in the resulting graph, and the capacity sum of the edges in C is the cut value of C. A minimum s−t edge cut is an s−t edge cut with the minimum cut value among all s−t edge cuts. A theorem given by Gomory and Hu states that there are only n−1 distinct values among the n(n−1)/2 minimum edge cuts in an edge-capacitated undirected graph G, and these distinct cuts can be compactly represented by a tree with the same node set as G, which is referred to the flow equivalent tree. In this paper we generalize their result to the node-edge cuts in a node-edge-capacitated undirected planar graph. We show that there is a flow equivalent tree for node-edge-capacitated undirected planar graphs, which represents the minimum node-edge cut for any pair of nodes in the graph through a novel transformation.     

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.     

Optimal many-to-one routing on the mesh with constant queues

We present randomized and deterministic algorithms for many-to-one packet routing on an n-node two-dimensional mesh under the store-and-forward model. We consider the general instance of many-to-one routing where each node is the source (resp., destination) of ? (resp., k) packets, for arbitrary values of ? and k. All our algorithms run in optimal time and use queues of only constant size at each node to store packets in transit. The randomized algorithms, however, are simpler to implement. Our result closes a gap in the literature, where time-optimal algorithms using constant-size queues were known only for the special cases ?=1 and ?=k.     

List edge and list total colorings of planar graphs without short cycles

Let G be a planar graph with maximum degree Δ(G). We use and to denote the list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that and if Δ(G)?6 and G has neither C₄ nor C₆, or Δ(G)?7 and G has neither C₅ nor C₆, where Ck is a cycle of length k.     

About acyclic edge colourings of planar graphs

Let G=(V,E) be any finite simple graph. A mapping is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced by all the edges which have either colour i or j is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .In 1991, Alon et al. [N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991) 277-288] proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed in [M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524-529].In this paper we prove that for a planar graph G without cycles of length three and that the same holds if G has an edge-partition into two forests. We also show that if G is planar.     

Note on the connectivity of line graphs

Let G be a connected graph with vertex set V(G), edge set E(G), vertex-connectivity κ(G) and edge-connectivity λ(G).A subset S of E(G) is called a restricted edge-cut if G−S is disconnected and each component contains at least two vertices. The restricted edge-connectivity λ₂(G) is the minimum cardinality over all restricted edge-cuts. Clearly λ₂(G)?λ(G)?κ(G).In 1969, Chartrand and Stewart have shown that

     

Vertex vulnerability parameters of Kronecker products of complete graphs

Let G₁ and G₂ be two graphs. The Kronecker product G₁×G₂ of G₁ and G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and edge set and v₁v₂∈E(G₂)}. In this paper, we determine some vertex vulnerability parameters of the Kronecker product of complete graphs Km×Kn for n?m?2 and n?3.     

Embedding paths and cycles in 3-ary n-cubes with faulty nodes and links

The k-ary n-cube, denoted by , is one of the most important interconnection networks for parallel computing. In this paper, we consider the problem of embedding cycles and paths into faulty 3-ary n-cubes. Let F be a set of faulty nodes and/or edges, and n?2. We show that when |F|?2n-2, there exists a cycle of any length from 3 to in . We also prove that when |F|?2n-3, there exists a path of any length from 2n-1 to between two arbitrary nodes in . Since the k-ary n-cube is regular of degree 2n, the fault-tolerant degrees 2n-2 and 2n-3 are optimal.     

Super connectivity of Kronecker products of graphs

Let G₁ and G₂ be two connected graphs. The Kronecker product G₁×G₂ has vertex set V(G₁×G₂)=V(G₁)×V(G₂) and the edge set . In this paper, we show that if G is a bipartite graph with κ(G)=δ(G), then G×Kn(n?3) is super-κ.     

On finding spanning trees with few leaves

The problem of finding a spanning tree with few leaves is motivated by the design of communication networks, where the cost of the devices depends on their routing functionality (ending, forwarding, or routing a connection). Besides this application, the problem has its own theoretical importance as a generalization of the Hamiltonian path problem. Lu and Ravi showed that there is no constant factor approximation for minimizing the number of leaves of a spanning tree, unless P=NP. Thus instead of minimizing the number of leaves, we are going to deal with maximizing the number of non-leaves: we give a linear-time 2-approximation for arbitrary graphs, a -approximation for claw-free graphs, and a -approximation for cubic graphs.