Irredundance trees of diameter 3

DOI10.1016/J.DISC.2022.113079MaRDI QIDQ2675840zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 26 September 2022

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

IR-graphIR-treeirredundancereconfiguration problem

Mathematics Subject Classification ID

Distance in graphs (05C12)

Abstract: A set D of vertices of a graph G with vertex set V is irredundant if each non-isolated vertex of G[D] has a neighbour in V-D that is not adjacent to any other vertex in D. The upper irredundance number IR(G) is the largest cardinality of an irredundant set of G; an IR(G)-set is an irredundant set of cardinality IR(G). The IR-graph of G has the IR(G)-sets as vertex set, and sets A and B are adjacent if and only if B can be obtained from A by exchanging a single vertex of A for an adjacent vertex in B. An IR-tree is an IR-graph that is a tree. We characterize IR-trees of diameter 3 by showing that these graphs are precisely the double stars S(2n,2n), i.e., trees obtained by joining the central vertices of two disjoint stars K_{1,2n}.

Recommendations

• Integral trees of diameter R (3 R 6)
• A lower bound for the irredundance number of trees
• The size of minimum 3-trees
• Integral trees of odd diameters
• The integral trees with spectral radius 3
• Integral trees of arbitrarily large diameters
• scientific article; zbMATH DE number 1043912
• A new lower bound for the irredundance number of a tree
• Indices of trees with a prescribed diameter
• Radius Three Trees in Graphs with Large Chromatic Number

Cites work

• -graphs of graphs
• A note on -graphs
• A note on some variations of the -graph
• Connected \(k\)-dominating graphs
• Gamma graphs of some special classes of trees
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 7272506 (Why is no real title available?)
• Induced subgraphs of gamma graphs
• Irredundance
• On the structure of dominating graphs
• Properties of Hereditary Hypergraphs and Middle Graphs
• Reconfiguring dominating sets in some well-covered and other classes of graphs
• The \(k\)-dominating graph
• The complexity of dominating set reconfiguration
• The gamma graph of a graph

Cited in

(1)

• Irredundance graphs

This page was built for publication: Irredundance trees of diameter 3

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