View Item 

Show simple item record

Matching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper‐stars
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:25Z
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 II: Cayley graphs generated by transposition trees and hyperâ stars." Networks 59(4): 357-364. <http://hdl.handle.net/2027.42/91319>en_US
dc.identifier.issn0028-3045en_US
dc.identifier.issn1097-0037en_US
dc.identifier.urihttps://hdl.handle.net/2027.42/91319
dc.description.abstractThe matching preclusion number of a graph with an even number of vertices is the minimum number of edges whose deletion results in a graph that has no perfect matchings. For many interconnection networks, the optimal sets are precisely those induced by a single vertex. It is natural to look for obstruction sets beyond those induced by a single vertex. The conditional matching preclusion number of a graph is the minimum number of edges whose deletion results in a graph with no isolated vertices that has no perfect matchings. In this companion paper of Cheng et al. (Networks (NET 1554)), we find these numbers for a number of popular interconnection networks including hypercubes, star graphs, Cayley graphs generated by transposition trees and hyper‐stars. © 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.otherCayley Graphsen_US
dc.subject.otherHyper‐Starsen_US
dc.titleMatching preclusion and conditional matching preclusion for bipartite interconnection networks II: Cayley graphs generated by transposition trees and hyper‐starsen_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.affiliationotherYale University, New Haven, Connecticut 06511en_US
dc.contributor.affiliationotherDepartment of Mathematics and Statistics, Oakland University, Rochester, Michigan 48309en_US
dc.contributor.affiliationotherDepartment of Mathematics and Statistics, Oakland University, Rochester, Michigan 48309en_US
dc.description.bitstreamurlhttp://deepblue.lib.umich.edu/bitstream/2027.42/91319/1/20441_ftp.pdf
dc.identifier.doi10.1002/net.20441en_US
dc.identifier.sourceNetworksen_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, L.H. Hsu, J. Tan, and C.K. Lin, Conditional matching preclusion for the star graphs, Ars Combin, (in press).en_US
dc.identifier.citedreferenceE. Cheng and M. Shah, A strong structural theorem for hyper‐stars, Congress Numer 80 ( 2006 ), 65 – 73.en_US
dc.identifier.citedreferenceJ. Kim, E. Oh, H. Lim, T. Heo, “Topological and communication aspects of hyper‐star graphs,” Lecture Notes in Comput. Sci. 2869, Springer, Berlin, 2003, pp. 51 – 58.en_US
dc.identifier.citedreferenceD. West, Introduction to graph theory, Prentice Hall, Upper Saddle River, NY, 1996.en_US
dc.identifier.citedreferenceH. Lee, J. Kim, E. Oh, and H. Lim, “Hyper‐star graph: A new interconnection network improving the network cost of the hypercube,”, Lecture Notes in Comput. Sci. 2510, Springer, Berlin, 2002, pp. 858 – 865.en_US
dc.identifier.citedreferenceS. Akers, D. Harel, and B. Krishnamurthy, “The star graph: An attractive alternative to the n ‐cube”, Proc. Int'l Conf. Parallel Processing, University Park, PA, USA, 1987, pp. 393 – 400.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, P. Hu, R. Jia, L. Lipták, Matching preclusion and conditional matching preclusion for bipartite interconnection networks I: Sufficient conditions, Networks, (NET 1554 will appear at the same time as this paper).en_US
dc.identifier.citedreferenceE. Cheng, P. Hu, R. Jia, L. Lipták, Matching preclusion and conditional matching preclusion for bipartite interconnection networks, Technical Report, Technical Reports Series 2009‐2, Oakland University, 2009.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 M. Lipman, Increasing the connectivity of the star graphs, Networks 40 ( 2002 ), 165 – 169.en_US
dc.identifier.citedreferenceE. Cheng and L. Lipták, Structural properties of Cayley graphs generated by transposition trees, Congress Numer 180 ( 2006 ), 81 – 96.en_US
dc.identifier.citedreferenceE. Cheng and L. Lipták, Structural properties of hyper‐stars, Ars Combin 80 ( 2006 ), 65 – 73.en_US
dc.identifier.citedreferenceE. Cheng and L. Lipták, Linearly many faults in Cayley graphs generated by transposition trees, Info Sci 177 ( 2007 ), 4877 – 4882.en_US
dc.identifier.citedreferenceX. Yang, D. Evans, and G. Megson, On the maximal connected component of hypercube with faulty vertices III, Int J Comput Math 83 ( 2006 ), 27 – 37.en_US
dc.identifier.citedreferenceX. Yang, D. Evans, and G. Megson, On the maximal connected component of hypercube with faulty vertices II, Int J Comput Math 81 ( 2004 ), 1175 – 1185.en_US
dc.identifier.citedreferenceX. Yang, D. Evans, B. Chen, G. Megson, and H. Lai, On the maximal connected component of hypercube with faulty vertices, Int J Comput Math 81 ( 2004 ), 515 – 525.en_US
dc.owningcollnameInterdisciplinary and Peer-Reviewed


Files in this item

Name:
20441_ftp.pdf
Size:
123.1KB
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.