View Item 

Show simple item record

Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions

dc.contributor.authorCheng, Eddieen_US
dc.contributor.authorHu, Philipen_US
dc.contributor.authorJia, Rogeren_US
dc.contributor.authorLipták, Lászlóen_US
dc.date.accessioned2012-06-15T14:32:48Z
dc.date.available2013-09-03T15:38:26Zen_US
dc.date.issued2012-07en_US
dc.identifier.citationCheng, Eddie; Hu, Philip; Jia, Roger; Lipták, László (2012). "Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions." Networks 59(4): 349-356. <http://hdl.handle.net/2027.42/91329>en_US
dc.identifier.issn0028-3045en_US
dc.identifier.issn1097-0037en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/91329
dc.description.abstractThe 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. This number 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 article, we prove general results regarding the matching preclusion number and the conditional matching preclusion number as well as the classification of their respective optimal sets for bipartite graphs. © 2011 Wiley Periodicals, Inc. NETWORKS, 2011en_US
dc.publisherWiley Subscription Services, Inc., A Wiley Companyen_US
dc.subject.otherInterconnection Networksen_US
dc.subject.otherPerfect Matchingen_US
dc.subject.otherBipartite Graphsen_US
dc.titleMatching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditionsen_US
dc.typeArticleen_US
dc.rights.robotsIndexNoFollowen_US
dc.subject.hlbsecondlevelManagementen_US
dc.subject.hlbsecondlevelIndustrial and Operations Engineeringen_US
dc.subject.hlbsecondlevelEconomicsen_US
dc.subject.hlbtoplevelBusinessen_US
dc.subject.hlbtoplevelEngineeringen_US
dc.description.peerreviewedPeer Revieweden_US
dc.contributor.affiliationumUniversity of Michigan, Ann Arbor, Michigan 48109en_US
dc.contributor.affiliationotherDepartment of Mathematics and Statistics, Oakland University, Rochester, Michigan 48309en_US
dc.contributor.affiliationotherYale University, New Haven, Connecticut 06511en_US
dc.contributor.affiliationotherDepartment of Mathematics and Statistics, Oakland University, Rochester, Michigan 48309en_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/91329/1/20440_ftp.pdf
dc.identifier.doi10.1002/net.20440en_US
dc.identifier.sourceNetworksen_US
dc.identifier.citedreferenceH. Hsu, Y. Hsieh, J. Tan, L. Hsu, Fault Hamiltonicity and fault Hamiltonian connectivity of the ( n, k )‐star graphs, Networks 42 ( 2003 ), 189 – 201.en_US
dc.identifier.citedreferenceH.C. Hsu, T.K. Li, J. Tan, and L.H. Hsu, Fault Hamiltonicity and fault Hamiltonian connectivity of the arrangement graphs, IEEE Trans Comput 53 ( 2004 ), 39 – 53.en_US
dc.identifier.citedreferenceT.K. Li, J. Tan, and L.H. Hsu, Hyper Hamiltonian laceability on edge fault star graph, Inf Sci 165 ( 2004 ), 59 – 71.en_US
dc.identifier.citedreferenceC. Balbuena, K. Marshall, and L.P. Montejano, On the connectivity and superconnected graphs with small diameter, Discrete Appl Math 158 ( 2010 ), 397 – 403.en_US
dc.identifier.citedreferenceD. Bauer, F. Boesch, C. Suffel, and R. Tindell, “Connectivity extremal problems and the design of reliable probabilistic networks,” The Theory and Application of Graphs, Y. Alavi and G. Chartrand (Editors), Wiley, New York, 1981, pp. 89 – 98.en_US
dc.identifier.citedreferenceF.T. Boesch, Synthesis of reliable networks—A survey, IEEE Trans Reliab 35 ( 1986 ), 240 – 246.en_US
dc.identifier.citedreferenceF.T. Boesch and R. Tindell, Circulants and their connectivities, J Graph Theory 8 ( 1984 ), 487 – 499.en_US
dc.identifier.citedreferenceR. Brigham, F. Harary, E. Violin, and J. Yellen, Perfect‐matching preclusion, Congress Numer 174 ( 2005 ), 185 – 192.en_US
dc.identifier.citedreferenceE. Cheng, L. Lesniak, M. Lipman, and L. Lipták, Matching preclusion for alternating group graphs and their generalizations, Int J Found Comput Sci 19 ( 2008 ), 1413 – 1437.en_US
dc.identifier.citedreferenceE. Cheng, L. Lesniak, M. Lipman, and L. Lipták, Conditional matching preclusion sets, Inf Sci 179 ( 2009 ), 1092 – 1101.en_US
dc.identifier.citedreferenceE. Cheng and L. Lipták, Matching preclusion for some interconnection networks, Networks 50 ( 2007 ), 173 – 180.en_US
dc.identifier.citedreferenceE. Cheng, L. Lipták, and D. Sherman, Matching preclusion for the ( n, k )‐bubble‐sort graphs, Int J Comput Math 87 ( 2010 ), 2408 – 2418.en_US
dc.identifier.citedreferenceM.A. Fiol, J. Fábrega, and M. Escudero, Short paths and connectivity in graphs and digraphs, Ars Combin 29B ( 1990 ), 17 – 31.en_US
dc.identifier.citedreferenceY.O. Hamidoune, A.S. Lladó, and O. Serra, Vosperian and superconnected abelian Cayley digraphs, Graphs Combin 7 ( 1991 ), 143 – 152.en_US
dc.identifier.citedreferenceS. Hsieh, G. Chen, and C. Ho, Fault‐free hamiltonian cycles in faulty arrangement graphs, IEEE Trans Parallel Distrib Syst 10 ( 1999 ), 223 – 237.en_US
dc.identifier.citedreferenceD. West, Introduction to graph theory, Prentice Hall, Upper Saddle River, NY, 1996.en_US
dc.identifier.citedreferenceJ. Plesník, Connectivity of regular graphs and the existence of 1‐factors, Matematický Časop 22 ( 1972 ), 310 – 318.en_US
dc.identifier.citedreferenceJ.H. Park and S. Son, Conditional matching preclusion for hypercube‐like interconnection networks, Theoret Comput Sci 410 ( 2009 ), 27 – 29.en_US
dc.identifier.citedreferenceJ.H. Park, Matching preclusion problem in restricted HL‐graphs and recursive circulant g (2 m, 4), J KIISE 35 ( 2008 ), 60 – 65.en_US
dc.identifier.citedreferenceX. Liang, J. Meng, and Z. Zhang, Super‐connectivity and hyper‐connectivity of vertex transitive bipartite graphs, Graphs Combin 23 ( 2007 ), 309 – 314.en_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Name:
20440_ftp.pdf
Size:
113.6KB
Format:
PDF
View/Open

Show simple item record

Remediation of Harmful Language

The University of Michigan Library aims to describe library materials in a way that respects the people and communities who create, use, and are represented in our collections. Report harmful or offensive language in catalog records, finding aids, or elsewhere in our collections anonymously through our metadata feedback form. More information at Remediation of Harmful Language.

Accessibility

If you are unable to use this file in its current format, please select the Contact Us link and we can modify it to make it more accessible to you.