On extension of regular graphs

DOI10.1080/09720529.2015.1085740MaRDI QIDQ5031864zbMATH OpenOpenAlexFDO

Authors Anirban Banerjee, Saptarshi Bej

Publication date 16 February 2022

Published in Journal of Discrete Mathematical Sciences and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1509.05476

zbMATH Keywords

bipartite regular graphextension of regularitymatching on regular graphregular graph

Mathematics Subject Classification ID

Vertex degrees (05C07) Connectivity (05C40) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

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 num- ber 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 dis- cussed, separately, for the extension of regularity.

Recommendations

• Graph extensions, edit number and regular graphs
• scientific article; zbMATH DE number 205826
• scientific article; zbMATH DE number 166088
• Minimal regular graph containing a given graph
• Note on regular subgraphs

Cites work

• A new 5‐arc‐transitive cubic graph
• Balloons, cut-edges, matchings, and total domination in regular graphs of odd degree
• Counting colorings of a regular graph
• Graph theory with applications
• Hamiltonian cycles in random regular graphs
• Matchings in regular graphs from eigenvalues
• On maximum matchings in almost regular graphs
• Random graphs.
• Regular graphs whose second largest eigenvalue is at most 1

Cited in

(9)

• Extensions on 2-edge connected 3-regular up-embeddable graphs
• Generating \(r\)-regular graphs
• Graph extensions, edit number and regular graphs
• 2-边连通3-正则非上可嵌入图的扩充
• Regular subgraphs of linear extension graphs.
• On the vertex irregular reflexive labeling of several regular and regular-like graphs
• On the extension of connected irregular (λ,μ)-graphs
• Coloring sums of extensions of certain graphs
• H-extension of graphs

This page was built for publication: On extension of regular graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5031864)