Please use this identifier to cite or link to this item: https://research.matf.bg.ac.rs/handle/123456789/1399
Title: On minimum rank of graphs with given dominating induced subgraphs
Authors: Stanić, Zoran 
Affiliations: Numerical Mathematics and Optimization 
Keywords: Adjacency matrix;Rank;Star complement;Path;Half graph;Cycle
Issue Date: 2024
Publisher: American Journal of Combinatorics(AJC)
Journal: American Journal of Combinatorics
Abstract: 
An induced subgraph of a graph G is said to be dominating if every vertex of G is at distance at most one from this subgraph. We investigate pairs (G, F ) where F is a nonsingular dominating induced subgraph of G, and the rank of G (that is, the rank of its adjacency matrix) attains the minimum, i.e., equals the number of vertices in F . It turns out that the inverse of the adjacency matrix of a nonsingular path, half graph, or even cycle is the adjacency matrix of a related signed graph; here, a half graph refers to a connected chain graph with exactly one vertex in each cell. We exploit this property to give a complete characterization of graphs G paired with any of these graphs in the role of F . The bipartite case is singled out. It occurs that every nonsingular F is paired with an infinite family of graphs G, and their number is comparatively large even if we exclude the existence of the so-called twin vertices. The latter empirical observation is demonstrated through some examples.
Description: 
Zoran Stanić: On minimum rank of graphs with given dominating induced subgraphs, American Journal of Combinatorics, (2024), Vol. 3, pp. 44-53
URI: https://research.matf.bg.ac.rs/handle/123456789/1399
Rights: Attribution 3.0 United States
Appears in Collections:Research outputs

Files in This Item:
File Description SizeFormat
V3.05.pdf332.54 kBAdobe PDF
View/Open
Show full item record

Page view(s)

22
checked on Dec 24, 2024

Download(s)

16
checked on Dec 24, 2024

Google ScholarTM

Check


This item is licensed under a Creative Commons License Creative Commons