Entity

Time filter

Source Type

Beverly Hills, MI, United States

Cheng E.,Oakland University | Jia R.,Detroit Country Day School | Lu D.,Detroit Country Day School
Journal of Interconnection Networks | Year: 2010

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 incident to a single vertex. Recently, the conditional matching preclusion number of a graph was introduced to look for obstruction sets beyond those incident to 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 augmented cubes, a class of networks designed as an improvement of the hypercubes. © 2010 World Scientific Publishing Company. Source


Cheng E.,Oakland University | Lu D.,Massachusetts Institute of Technology | Xu B.,Detroit Country Day School
Journal of Interconnection Networks | Year: 2013

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 that was introduced by Park and Ihm. In this paper, we examine the properties of pancake graphs by finding its strong matching preclusion number and categorizing all optimal solutions. © 2013 World Scientific Publishing Company. Source


Yuan A.,Detroit Country Day School | Cheng E.,Oakland University | Liptak L.,Oakland University
International Journal of Foundations of Computer Science | Year: 2011

The star graph proposed by [1] has many advantages over the n-cube. However it suffers from having large gaps in the number of possible vertices. The (n,k)-star graph was proposed in [18] to address this issue. Since it is a generalization of the star graph, it retains many of the nice properties of the star graph. There are many different measures of structural integrity of interconnection networks. In this paper, we prove results of the following type for the (n,k)-star graph. If n + (r - 1)k - g(r) vertices are deleted from an (n,k)-star graph, the resulting graph will either be connected or has a large component and small components having at most r - 1 vertices in total. Additional results on conditional vertex connectivity and cycle connectivity will also be given. © 2011 World Scientific Publishing Company. Source


Hung C.-N.,Da - Yeh University | Lu D.,Detroit Country Day School | Jia R.,Detroit Country Day School | Lin C.-K.,National Chiao Tung University | And 4 more authors.
Mathematical and Computer Modelling | Year: 2013

A graph G is k-ordered if for every sequence of k distinct vertices of G, there exists acycle in G containing these k vertices in the specified order. It is k-ordered-Hamiltonian if, in addition, the required cycle is a Hamiltonian cycle in G. The question of the existence of an infinite class of 3-regular 4-ordered-Hamiltonian graphs was posed in Ng and Schultz in 1997 [2]. At the time, the only known examples of such graphs were K4 and K3,3. Some progress was made by Mészáros in 2008 [21] when the Petersen graph was found to be 4-ordered and the Heawood graph was proved to be 4-ordered-Hamiltonian; moreover, an infinite class of 3-regular 4-ordered graphs was found. In 2010, asubclass of the generalized Petersen graphs was shown to be 4-ordered in Hsu etal. [9], with an infinite subset of this subclass being 4-ordered-Hamiltonian, thus answering the open question. However, these graphs are bipartite. In this paper we extend the result to another subclass of the generalized Petersen graphs. In particular, we find the first class of infinite non-bipartite graphs that are both 4-ordered-Hamiltonian and 4-ordered-Hamiltonian-connected, which can be seen as a solution to an extension of the question posted in Ng and Schultz in 1997 [2]. (A graph G is k-ordered-Hamiltonian-connected if for every sequence of k distinct vertices a1, a2,..., ak of G, there exists a Hamiltonian path in G from a1 to ak where these k vertices appear in the specified order.). © 2012 Elsevier Ltd. Source

Discover hidden collaborations