New upper bounds on feedback vertex numbers in butterflies

Butterflies are undirected graphs of bounded degree. They are widely used as interconnection networks. In this paper we study the feedback vertex set problem for butterflies. We show that the feedback vertex set found by Luccio's algorithm [Inform. Process. Lett. 66 (1998) 59–64] for the k-dimensional butterfly B_k is of size . Besides, we propose an algorithm to find a feedback vertex set of size either or for B_k depending on whether k is even or odd.     

Edge-bipancyclicity of star graphs with faulty elements

In this paper, we investigate the fault-tolerant edge-bipancyclicity of an n-dimensional star graph S_n. Given a set F comprised of faulty vertices and/or edges in S_n with |F|≤n−3 and any fault-free edge e in S_n−F, we show that there exist cycles of every even length from 6 to n!−2|F_v| in S_n−F containing e, where n≥3. Our result is optimal because the star graph is both bipartite and regular with the common degree n−1. The length of the longest fault-free cycle in the bipartite S_n is n!−2|F_v| in the worst case, where all faulty vertices are in the same partite set. We also provide some sufficient conditions from which longer cycles with length from n!−2|F_v|+2 to n!−2|F_v| can be embedded.     

An efficient algorithm for minimum feedback vertex sets in rotator graphs

For a rotator graph with n! nodes, Hsu and Lin [C.C. Hsu, H.R. Lin, H.C. Chang, K.K. Lin, Feedback Vertex Sets in Rotator Graphs, in: Lecture Notes in Comput. Sci., vol. 3984, 2006, pp. 158-164] first proposed an algorithm which constructed a feedback vertex set (FVS) with time complexity O(nn−3). In addition, they found that the size of the FVS is n!/3, which was proved to be minimum. In this paper, we present an efficient algorithm which constructs an FVS for a rotator graph in O(n!) time and also obtains the minimum FVS size n!/3. In other words, this algorithm derives the optimal result with linear time complexity in terms of the number of nodes in the rotator graph.     

Large independent sets in random regular graphs

We present algorithmic lower bounds on the size _sd$s_d$ of the largest independent sets of vertices in random d$d$-regular graphs, for each fixed d≥3$d\ge 3$. For instance, for d=3$d=3$ we prove that, for graphs on n$n$ vertices, _sd≥0.43475n$s_d\ge 0.43475n$ with probability approaching one as n$n$ tends to infinity.     

Minimum weight feedback vertex sets in circle graphs

We describe a polynomial time algorithm to find a minimum weight feedback vertex set, or equivalently, a maximum weight induced forest, in a circle graph. The circle graphs are the overlap graphs of intervals on a line.     

Diagnosability of star graphs under the comparison diagnosis model

In this paper, the diagnosability of n-dimensional star graph Sn under the comparison diagnosis model has been studied. It is proved that Sn is (n−1)-diagnosable under the comparison diagnosis model when n?4.     

Linear election in pancake graphs

Pancake graphs have been proposed as an attractive alternative to hypercube networks. They have a smaller diameter and a lower degree. They also have a hierarchical structure which can be exploited in designing algorithms.In this paper, we propose a leader election algorithm for oriented pancake graphs. The algorithm has a message complexity that is linear in the order of the graph.     

Counting maximal independent sets in directed path graphs

The problem of counting maximal independent sets is #P-complete for chordal graphs but solvable in polynomial time for its subclass of interval graphs. This work improves upon both of these results by showing that the problem remains #P-complete when restricted to directed path graphs but that a further restriction to rooted directed path graphs admits a polynomial time solution.     

Linearly many faults in Cayley graphs generated by transposition trees

We prove that when linearly many vertices are deleted in a Cayley graph generated by a transposition tree, the resulting graph has a large connected component containing almost all remaining vertices.     

Honeycomb toroidal graphs are Cayley graphs

There is a particular family of trivalent vertex-transitive graphs that have been called generalized honeycomb tori by some and brick products by others. They have been studied as hexagonal embeddings on the torus as well. We show that all these graphs are Cayley graphs on generalized dihedral groups.     

A study of fault tolerance in star graph

The bounds on f(n,k), the number of faulty nodes to make every (n−k)-dimensional substar Sn−k in an n-dimensional star network Sn, have been derived. The exact value for f(n,k) is determined when n is prime and k=2, or when n−2?k?n. For 2<k<n−2, a general method is presented to derive a set of faulty nodes which damage all Sn−k's in Sn.     

A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees

Let G be a graph. Then T ⊆ V(G) is called an R^k-vertex-cut if G − T is disconnected and each vertex in V(G) − T has at least k neighbors in G − T. The size of a smallest R^k-vertex-cut is the R^k-vertex-connectivity of G and is denoted by κ^k(G). In this paper, we determine the numbers κ¹ and κ² for Cayley graphs generated by 2-trees, including the popular alternating group graphs.     

On handshakes in random graphs

In [Y. Métivier, N. Saheb, A. Zemmari, Analysis of a randomized rendezvous algorithm, Inform. and Comput. 184 (2003) 109-128], the authors introduce and analyze a randomized procedure to implement handshakes in graphs. In this paper, we investigate the same problem in random graphs. We prove results on the probability of success and we study the distribution of the random variable which counts the number of handshakes in the graph.     

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 probabilistic algorithm for vertex connectivity of graphs

A probabilistic algorithm is presented which computes the vertex connectivity of an undirected graph G = (V,E) in expected time $\text{O((-log ε|V|}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}\text{|E|)}$ with error probability at most e provided that |E|<frcase|1/2d|V|² for some universal constant d<1.     

Pancyclicity of recursive circulant graphs

In this paper, we study the existence of cycles of all lengths in the recursive circulant graphs, and we show a necessary and sufficient condition for the graph being pancyclic and bipancyclic.     

Conditional matching preclusion for the arrangement graphs

The matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those induced by a single vertex. It is defined to be the minimum number of edges whose deletion results in a graph with no isolated vertices that has neither perfect matchings nor almost-perfect matchings. In this paper we find this number and classify all optimal sets for the arrangement graphs, one of the most popular interconnection networks.     

A note on maximum independent set and related problems on box graphs

A box graph is the intersection graph of orthogonal rectangles in the plane. We show that maximum independent set and minimum vertex cover on box graphs can be solved in subexponential time, more precisely, in time , by applying Miller's simple cycle planar separator theorem [J. Comput. System Sci. 32 (1986) 265-279] (in spite of the fact that the input box graph might be strongly non-planar).