A characterization of graphs with regular distance-2 graphs

DOI10.1016/J.DAM.2022.09.020MaRDI QIDQ2097182zbMATH OpenOpenAlexFDO

Authors Elisabeth Gaar, Daniel Krenn

Publication date 11 November 2022

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

Copyright license Creative Commons Attribution 4.0 International

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

zbMATH Keywords

characterizationjoin of graphsregular graphsunlabeled graphs

Mathematics Subject Classification ID

Distance in graphs (05C12) Association schemes, strongly regular graphs (05E30)

Abstract: For non-negative integers~$k$, we consider graphs in which every vertex has exactly $k$ vertices at distance~$2$, i.e., graphs whose distance-$2$ graphs are $k$-regular. We call such graphs $k$-metamour-regular motivated by the terminology in polyamory. While constructing $k$-metamour-regular graphs is relatively easy -- we provide a generic construction for arbitrary~$k$ -- finding all such graphs is much more challenging. We show that only $k$-metamour-regular graphs with a certain property cannot be built with this construction. Moreover, we derive a complete characterization of $k$-metamour-regular graphs for each $k=0$, $k=1$ and $k=2$. In particular, a connected graph with~$n$ vertices is $2$-metamour-regular if and only if $nge5$ and the graph is a join of complements of cycles (equivalently every vertex has degree~$n-3$), a cycle, or one of $17$ exceptional graphs with $nle8$. Moreover, a characterization of graphs in which every vertex has at most one metamour is acquired. Each characterization is accompanied by an investigation of the corresponding counting sequence of unlabeled graphs.

Recommendations

• On \((r, 2, (r - 1)(r - 1))\)-regular graphs
• Characterizing 2-distance graphs
• The characterization of all (2,3)-regular graphs
• Distance-regular graphs with \(\Gamma(x) \simeq 3* K_{a+1}\)
• scientific article; zbMATH DE number 867673

Cites work

• 2-distance coloring of sparse graphs
• 2-distance coloring of sparse planar graphs
• 2-distance coloring of sparse planar graphs
• 2-distance vertex-distinguishing index of subcubic graphs
• A bound on the chromatic number of the square of a planar graph
• A survey on the distance-colouring of graphs
• Characterizing 2-distance graphs
• Distance-2 domatic numbers of grid graphs
• Distance-regular graphs with diameter 3 and eigenvalue \(a_2 - c_3\)
• Distributed-memory parallel algorithms for distance-2 coloring and related problems in derivative computation
• Graph theory
• Graph theory
• scientific article; zbMATH DE number 3834025 (Why is no real title available?)
• scientific article; zbMATH DE number 43547 (Why is no real title available?)
• scientific article; zbMATH DE number 3634304 (Why is no real title available?)
• scientific article; zbMATH DE number 758277 (Why is no real title available?)
• scientific article; zbMATH DE number 5174935 (Why is no real title available?)
• scientific article; zbMATH DE number 6471182 (Why is no real title available?)
• scientific article; zbMATH DE number 3290993 (Why is no real title available?)
• On k-domatic numbers of graphs
• On graphs with Hamiltonian squares
• Self 2-distance graphs
• The Chromatic Number of Graph Powers

Cited in

(7)

• Algebraic characterizations of distance-regular graphs
• Two distance-regular graphs
• A family of weakly distance-regular digraphs of girth 2
• Two results concerning distance-regular directed graphs
• A CHARACTERIZATION FOR METRIC TWO-DIMENSIONAL GRAPHS AND THEIR ENUMERATION
• Connectivity of 3-distance graphs
• The classification of distance-regular graphs of type IIB

Describes a project that uses

Uses Software

• MathOverflow
• OEIS

This page was built for publication: A characterization of graphs with regular distance-2 graphs

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