Journal of Interconnection Networks

The strong matching preclusion number of a graph is the minimum number of vertices and edges whose deletion results in a graph that has neither perfect matchings nor almost-perfect matchings. This is an extension of the matching preclusion problem and has recently been introduced by Park and Ihm.¹⁵ In this paper, we examine properties of strong matching preclusion for alternating group graphs, by finding their strong matching preclusion numbers and categorizing all optimal solutions. More importantly, we prove a general result on taking a Cartesian product of a graph with K₂ (an edge) to obtain the corresponding results for split-stars.

Reducing the size of IP routing tables is one of the most compelling scaling problems affecting the Internet because of massive growth of routing table entries, increased traffic, and the migration to 128 bit IPv6 addresses. Various algorithms for IP table minimization have been proposed in the literature both for a single and for multiple tables, also with the possibility of performing address reassignments. In this paper we first introduce two new compression heuristics, the BFM and its evolution called BFM-Cluster, that exploit address reassignments for the minimization of multiple routing tables, and then we experimentally evaluate their performances together with the already existing techniques. Since a main problem posed by the growth of the routing tables sizes is the consequent general increase of the table lookup time during the routing of the IP packets, the aim is twofold: to measure and compare the compression ratios of the different algorithms, and to estimate the effects of the compression on the lookup times by measuring the induced improvement on the time of the main algorithms and data structures for the fast IP address lookup from the original tables to the compressed ones. Our point is that the existing techniques are efficient in different situations, with BFM-Cluster heuristic outperforming all other ones.

In this paper we formulate the Vertex Congestion Lemma leading to a new technique in computing the exact wirelength of an embedding. We compute the circular wirelength of generalized Petersen graphs by partitioning the vertices as well as the edges of cycles. Further we obtain the linear wirelength of circular ladders. Our algorithms produce optimal values in linear time.

In this paper, we consider the conditionally faulty graphs G that each vertex of G is incident with at least m fault-free edges, 2 ≤ m ≤ n - 1. We extend the limitation m ≥ 2 in all previous results of edge-bipancyclicity with faulty edges and faulty vertices. Let f_e (respectively, f_v) denotes the number of faulty edges (respectively, faulty vertices) in an n-dimensional hypercube Q_n. For all m, we show that every fault-free edge of Q_n lies on a fault-free cycle of every even length from 4 to |V| - 2f_v inclusive provided f_e + f_v ≤ n - 2. This result is not only optimal, but also improves on the previously best known results reported in the literature.