2018/12/08 by Kieka Mynhardt, Mynhardt, Kieka, Riana Roux +1
Computer Science · Engineering · Mathematics · #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #graph theory and CDMA systems #math.CO #msc:05C69
paper · pdf · doi:10.48550/arxiv.1812.03382
19 pages, 4 figures
openalex publication_date 2018/12/08 · openalex created_date 2020/04/24 · arxiv created 2021/04/07 · arxiv updated 2021/04/08 · openalex updated_date 2026/07/28
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.