Cited By
View all- Wang XYuan JZhou S(2009)Edge-deletable IM-extendable graphs with minimum number of edgesDiscrete Mathematics10.1016/j.disc.2009.03.048309:16(5242-5247)Online publication date: 1-Aug-2009
Induced Matching Extendable Graph Powers
Pages 391 - 398
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.
Index Terms
- Induced Matching Extendable Graph Powers
Recommendations
Induced matching extendable graphs
We say that a simple graph G is induced matching extendable, shortly IM-extendable, if every induced matching of G is included in a perfect matching of G. The main results of this paper are as follows:
(1) For every connected IM-extendable graph G with |...
Graph powers and k-ordered Hamiltonicity
It is known that if G is a connected simple graph, then G^3 is Hamiltonian (in fact, Hamilton-connected). A simple graph is k-ordered Hamiltonian if for any sequence v"1, v"2,...,v"k of k vertices there is a Hamiltonian cycle containing these vertices ...
Parameterized Complexity of Induced Graph Matching on Claw-Free Graphs
The Induced Graph Matching problem asks to find $$k$$ k disjoint induced subgraphs isomorphic to a given graph $$H$$ H in a given graph $$G$$ G such that there are no edges between vertices of different subgraphs. This problem generalizes the classical Independent Set and ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 01 November 2006
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Nov 2024
Other Metrics
Citations
Cited By
View all- Wang XYuan JZhou S(2009)Edge-deletable IM-extendable graphs with minimum number of edgesDiscrete Mathematics10.1016/j.disc.2009.03.048309:16(5242-5247)Online publication date: 1-Aug-2009
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in