On extension of regular graphs
- 2 January 2018
- journal article
- research article
- Published by Taru Publications in Journal of Discrete Mathematical Sciences & Cryptography
- Vol. 21 (1), 13-21
- https://doi.org/10.1080/09720529.2015.1085740
Abstract
In this article, we discuss when one can extend an r-regular graph to an r + 1 regular by adding edges. Different conditions on the number of vertices n and regularity r are developed. We derive an upper bound of r, depending on n, for which, every regular graph G(n, r) can be extended to an r + 1-regular graph with n vertices. Presence of induced complete bipartite subgraph and complete subgraph is discussed, separately, for the extension of regularity.Keywords
Other Versions
This publication has 3 references indexed in Scilit:
- Balloons, cut‐edges, matchings, and total domination in regular graphs of odd degreeJournal of Graph Theory, 2009
- Complex brain networks: graph theoretical analysis of structural and functional systemsNature Reviews Neuroscience, 2009
- Random GraphsPublished by Cambridge University Press (CUP) ,2001