Name
Abstract | ||
|---|---|---|
A matching M of a graph G is a dominating induced matching DIM of G if every edge of G is either in M or adjacent with exactly one edge in M. We prove sharp upper bounds on the number µG of DIMs of a graph G and characterize all extremal graphs. Our results imply that if G is a graph of order n, then µG﾿3n3; µG﾿4n5 provided G is triangle-free; and µG﾿4n-15 provided n﾿9 and G is connected. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1002/jgt.21804 | Journal of Graph Theory |
Keywords | Field | DocType |
dominating induced matching,Fibonacci numbers | Graph,Topology,Discrete mathematics,Dominating set,Combinatorics,Graph power,Bound graph,Graph factorization,Bipartite graph,Factor-critical graph,Blossom algorithm,Mathematics | Journal |
Volume | Issue | ISSN |
78 | 4 | 0364-9024 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Min Chih Lin | 1 | 259 | 21.22 |
| Veronica A. Moyano | 2 | 1 | 1.03 |
| Dieter Rautenbach | 3 | 946 | 138.87 |
| Jayme Luiz Szwarcfiter | 4 | 618 | 95.79 |