Back to Search
Start Over
VERTICES BELONGING TO ALL CRITICAL SETS OF A GRAPH.
- Source :
-
SIAM Journal on Discrete Mathematics . 2012, Vol. 26 Issue 1, p399-403. 5p. - Publication Year :
- 2012
-
Abstract
- Let G = (V, E) be a graph. A set S⊆V is independent if no two vertices from are adjacent, while core(G) is the intersection of all maximum independent sets [V. E. Levit and E. Mandrescu, Discrete Appl. Math., 117 (2002), pp. 149-161]. The independence number α(G)is the cardinality of a largest independent set, and µ(G) is the size of a maximum matching of G. The neighborhood of A⊆V is N(A)= {v ∈ V : N(v)∩=0. The number dc(G)=max{|X|-|N(X)| : X ⊆ V} is called the critical di?erence of G, and is critical if |A|-|N(A)| = dc(G) [C. Q. Zhang, SIAM J. Discrete Math., 3 (1990), pp. 431-438]. We define ker(G) as the intersection of all critical sets. In this paper we prove that if dc(G) ≥ 1, then ker(G) ⊆ core(G) and |ker(G)| >dc(G) ≥ α(G)-µ(G). [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH theory
*INTERSECTION graph theory
*MATHEMATICS
*SET theory
*CARDINAL numbers
Subjects
Details
- Language :
- English
- ISSN :
- 08954801
- Volume :
- 26
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- SIAM Journal on Discrete Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- 76622325
- Full Text :
- https://doi.org/10.1137/110823560