Common Independence in Graphs
Open Access
Abstract
The cardinality of a largest independent set of G, denoted by , is called the independence number of G. The independent domination number of a graph G is the cardinality of a smallest independent dominating set of G. We introduce the concept of the common independence number of a graph G, denoted by , as the greatest integer r such that every vertex of G belongs to some independent subset X of with . The common independence number of G is the limit of symmetry in G with respect to the fact that each vertex of G belongs to an independent set of cardinality in G, and there are vertices in G that do not belong to any larger independent set in G. For any graph G, the relations between above parameters are given by the chain of inequalities . In this paper, we characterize the trees T for which , and the block graphs G for which .
Keywords
This publication has 7 references indexed in Scilit:
- Graph Theory: A Comprehensive Survey about Graph Theory Applications in Computer Science and Social NetworksInventions, 2020
- Independent domination in graphs: A survey and recent resultsDiscrete Mathematics, 2013
- On weakly connected domination in graphs IIDiscrete Mathematics, 2005
- Paired-domination in graphsNetworks, 1998
- WELL-COVERED GRAPHS: A SURVEYQuaestiones Mathematicae, 1993
- Some covering concepts in graphsJournal of Combinatorial Theory, 1970
- Theory of Graphs1962