Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Induced Matching Extendable Graph Powers

  • Published:
Graphs and Combinatorics Aims and scope Submit manuscript

Abstract

A graph G is called induced matching extendable (shortly, IM-extendable) if every induced matching of G is included in a perfect matching of G. A graph G is called strongly IM-extendable if every spanning supergraph of G is IM-extendable. The k-th power of a graph G, denoted by Gk, is the graph with vertex set V(G) in which two vertices are adjacent if and only if the distance between them in G is at most k.

We obtain the following two results which give positive answers to two conjectures of Yuan.

Result 1. If a connected graph G with |V(G)| even is locally connected, then G2 is strongly IM-extendable.

Result 2. If G is a 2-connected graph with |V(G)| even, then G3 is strongly IM-extendable.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Bondy, J.A., Murty, U.S.R.: Graph Theory with Applications, London: Macmillan Press Ltd 1976

  2. Cameron, K.: Induced matchings. Discrete Appl. Math. 24, 97–102 (1989)

  3. Faudree, R.T., Gyarfas, A., Schelp, R.M., Tuza, Z.: Induced matchings in bipartite graphs. Disrete Math. 78, 83–87 (1989)

    Google Scholar 

  4. Liu, Y., Yuan, J.J., Wang, S.Y.: Degree conditions of IM-extendable graphs. Appl. Math.–JCU. 15B(1), 1–6 (2000)

  5. Lovász, L., Plummer, M.D.: Matching Theory. B. V. North Holland: Elsevier Science Publishers 1985

  6. Wang, Q., Yuan, J.J.: Maximal IM-unextendable graphs, Discrete Math. 240, 295–298 (2001)

    Google Scholar 

  7. Yang, F., Yuan, J.J.: Induced matching extendable graphs without K4 minor, in: Advances in Operations Research and Systems Engineering (Edited by J.F. Gu, G.H. Fan, S.Y. Wang and B. Wei), 1998, 142–145

  8. Yang, F., Yuan, J.J.: NP-completeness of induced matching problem and co-NP-completeness of induced matching extendable problem, OR Transactions. 4(1), 76–80 (2000)

    Google Scholar 

  9. Yuan, J.J.: Induced matching extendable graphs, J. Graph Theory 28, 203–213 (1998)

    Google Scholar 

  10. Yuan, J.J.: Three conjectures on the IM-extendability of the power of a graph, Privite communication

  11. Yuan, J.J.: Induced matching extendable graphs - A survey, Invited Report of the 6th Conference on Operation Research of China, Changsha, China, 2000

  12. Yuan, J.J.: Independent-set-deletable factor-critical graph powers, In submission

  13. Yuan, J.J. and Wang, Q.: Induced matching extendability of G3, Graph Theory Notes of New York, XLIII, 16–19 (2002)

Download references

Author information

Authors and Affiliations

  1. Mathematics & Science College, Xiamen University, Xiamen, Fujian, 361005, P. R. China

    Jianguo Qian

Authors
  1. Jianguo Qian
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Jianguo Qian.

Additional information

Research Supported by NSFC Fund 10371102.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Qian, J. Induced Matching Extendable Graph Powers. Graphs and Combinatorics 22, 391–398 (2006). https://doi.org/10.1007/s00373-006-0673-0

Download citation

  • Received:

  • Accepted:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s00373-006-0673-0

Keywords

AMS Subject Classifications

Search

Navigation