Irredundance graphs

DOI10.1016/J.DAM.2022.08.005MaRDI QIDQ2081464zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 13 October 2022

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

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

zbMATH Keywords

IR-graphirredundancereconfiguration problem

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: A set D of vertices of a graph G=(V,E) is irredundant if each v of D satisfies (a) v is isolated in the subgraph induced by D, or (b) v is adjacent to a vertex in V-D that is nonadjacent to all other vertices 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 D and D' are adjacent if and only if D' is obtained from D by exchanging a single vertex of D for an adjacent vertex in D'. We study the realizability of graphs as IR-graphs and show that all disconnected graphs are IR-graphs, but some connected graphs (e.g. stars of order three or more, the paths of order 4 or 5, the 5-cycle) are not.

Recommendations

• Irredundance trees of diameter 3
• scientific article; zbMATH DE number 140135
• Total irredundance in graphs
• (k,r)-Irredundant sets in graphs
• A note on graphs which have upper irredundance equal to independence

Cites work

• -graphs of graphs
• A note on -graphs
• A note on some variations of the -graph
• Classifying coloring graphs
• Connected \(k\)-dominating graphs
• Connectedness of the graph of vertex-colourings
• Finding paths between 3-colorings
• Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances
• Gamma graphs of some special classes of trees
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• Induced subgraphs of gamma graphs
• Irredundance trees of diameter 3
• On the complexity of reconfiguration problems
• On the structure of dominating graphs
• Properties of Hereditary Hypergraphs and Middle Graphs
• Reconfiguration of list edge-colorings in a graph
• 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

(19)

• Changing upper irredundance by edge addition
• Well irredundant graphs
• Bipartite theory of irredundant set
• (k,r)-Irredundant sets in graphs
• The upper irredundance number of the crown
• OC-irredundance, CO-irredundance and maximum degree in trees
• Irredundance saturation number of a graph
• scientific article; zbMATH DE number 140135 (Why is no real title available?)
• Irredundance in inflated graphs
• scientific article; zbMATH DE number 2061807 (Why is no real title available?)
• scientific article; zbMATH DE number 1506498 (Why is no real title available?)
• scientific article; zbMATH DE number 1792610 (Why is no real title available?)
• scientific article; zbMATH DE number 7059509 (Why is no real title available?)
• Irreducible graphs
• scientific article; zbMATH DE number 2188352 (Why is no real title available?)
• Depicting the Redundancy of Fourth Figure Using Venn-Peirce Framework
• γ-Paired dominating graphs of lollipop, umbrella and coconut graphs
• Irredundancy in circular arc graphs
• A note on graphs which have upper irredundance equal to independence

This page was built for publication: Irredundance graphs

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