Graph extensions, edit number and regular graphs

DOI10.1016/J.DAM.2018.10.042MaRDI QIDQ1732121zbMATH OpenOpenAlexWikidataFDO

Authors Ghurumuruhan Ganesan

Publication date 22 March 2019

Published in Discrete Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

connected regular graphsedit number of graphsgraph extensions

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Connectivity (05C40)

Abstract: A graph G on n vertices is said to be extendable if G can be modified to form a new graph H on more than n vertices, while preserving the degrees of the vertices common to G and H. The added vertices all have the same degree and we define edit numbers to quantify the amount of modification needed to obtain the extended graph. Characterizing graphs with least possible edit numbers, we obtain that graphs with zero edit number can be extended using regular graphs. We also describe an iterative algorithm to construct connected regular graphs on arbitrarily large vertex sets, starting from the complete graph on a fixed set of vertices.

Recommendations

• On extension of regular graphs
• scientific article; zbMATH DE number 166088
• \(n\)-regular \((n-2)\)-edge deletable IM-extendable graphs
• Characterization of graphs with a given number of additional edges in a minimal 1-vertex extension
• Editing to a connected graph of given degrees

Cites work

• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 1943957 (Why is no real title available?)
• A fast matching algorithm for graph-based handwriting recognition
• A note on a theorem of Erdős and Gallai
• A remark on the existence of finite graphs
• A survey of graph edit distance
• Existence of k-edge connected ordinary graphs with prescribed degrees
• Finding a -regular supergraph of minimum order
• Fixed-parameter tractable distances to sparse graph classes
• On Realizability of a Set of Integers as Degrees of the Vertices of a Linear Graph. I
• Regular graphs containing a given graph

Cited in

(1)

• On extension of regular graphs

This page was built for publication: Graph extensions, edit number and regular graphs

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