Regular PapersNo Access

MATCHING PRECLUSION FOR ALTERNATING GROUP GRAPHS AND THEIR GENERALIZATIONS

EDDIE CHENG

Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA

Corresponding author.

Search for more papers by this author

LINDA LESNIAK

Department of Mathematics and Computer Science, Drew University, Madison, NJ 07940, USA

Search for more papers by this author

MARC J. LIPMAN

College of Arts and Sciences, Indiana University—Purdue University, Fort Wayne, Fort Wayne, IN 46805, USA

Search for more papers by this author

, and

LÁSZLÓ LIPTÁK

Department of Mathematics and Statistics, Oakland University, Rochester, MI 48309, USA

Search for more papers by this author

https://doi.org/10.1142/S0129054108006364Cited by:46 (Source: Crossref)

Abstract

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. In this paper, we find this number for the alternating group graphs, Cayley graphs generated by 2-trees and the (n,k)-arrangement graphs. Moreover, we classify all the optimal solutions.

Keywords:

References

S. B. Akers, D. Harel and B. Krishnamurthy, The star graph: An attractive alternative to the n-cube, Proc. Int'l Conf. Parallel Processing (1987) pp. 393–400. Google Scholar
T. Araki, Networks 48, 121 (2006), DOI: 10.1002/net.20126. Crossref, Web of Science, Google Scholar
L. W. Beineke and R. E. Pippert, Journal of Combinatirial Theory 6, 200 (1969), DOI: 10.1016/S0021-9800(69)80120-1. Crossref, Web of Science, Google Scholar
L. W. Beineke and R. E. Pippert, Mathematika 18, 141 (1971). Crossref, Web of Science, Google Scholar
R. C. Brighamet al., Congressus Numerantium 174, 185 (2005). Google Scholar
E. Cheng et al. , Mathematical and Computer Modelling . Google Scholar
E. Cheng, M. J. Lipman and H. A. Park, Ars Combinatoria 59, 107 (2001). Web of Science, Google Scholar
E. Cheng and L. Lipták, Networks 50, 173 (2007), DOI: 10.1002/net.20187. Crossref, Web of Science, Google Scholar
W. K. Chiang and R. J. Chen, Inform. Proc. Lett. 56, 259 (1995). Web of Science, Google Scholar
K. Day and A. Tripathi, Inform. Proc. Lett. 42, 235 (1992), DOI: 10.1016/0020-0190(92)90030-Y. Crossref, Web of Science, Google Scholar
H.-C. Hsuet al., IEEE Transactions on Computers 53, 39 (2004). Web of Science, Google Scholar
J. S. Jwo, S. Lakshmivarahan and S. K. Dhall, Networks 23, 315 (1993), DOI: 10.1002/net.3230230414. Crossref, Web of Science, Google Scholar