A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical
Let γ c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-γ c -critical if γ c (G) = k, but γ c (G + xy) < k for xy Î E([`(G)])xyE(G) . Further, for integer r ≥ 2, G is said to be k-(γ c , r)-critical if γ c (G) = k, but γ c (G + xy) < k for each pair of no...
| Main Authors: | , , |
|---|---|
| Format: | Journal Article |
| Published: |
Springer Japan KK
2010
|
| Subjects: | |
| Online Access: | http://hdl.handle.net/20.500.11937/19085 |
| _version_ | 1848749932346867712 |
|---|---|
| author | Ananchuen, Watcharaphong Ananchuen, Nawarat Caccetta, Louis |
| author_facet | Ananchuen, Watcharaphong Ananchuen, Nawarat Caccetta, Louis |
| author_sort | Ananchuen, Watcharaphong |
| building | Curtin Institutional Repository |
| collection | Online Access |
| description | Let γ c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-γ c -critical if γ c (G) = k, but γ c (G + xy) < k for xy Î E([`(G)])xyE(G) . Further, for integer r ≥ 2, G is said to be k-(γ c , r)-critical if γ c (G) = k, but γ c (G + xy) < k for each pair of non-adjacent vertices x and y that are at distance at most r apart. k-γ c -critical graphs are k-(γ c , r)-critical but the converse need not be true. In this paper, we give a characterization of 3-(γ c , 2)-critical claw-free graphs which are not 3-γ c -critical. In fact, we show that there are exactly four classes of such graphs. |
| first_indexed | 2025-11-14T07:28:47Z |
| format | Journal Article |
| id | curtin-20.500.11937-19085 |
| institution | Curtin University Malaysia |
| institution_category | Local University |
| last_indexed | 2025-11-14T07:28:47Z |
| publishDate | 2010 |
| publisher | Springer Japan KK |
| recordtype | eprints |
| repository_type | Digital Repository |
| spelling | curtin-20.500.11937-190852017-09-13T16:03:34Z A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical Ananchuen, Watcharaphong Ananchuen, Nawarat Caccetta, Louis Critical graph Connected domination Claw-free Let γ c (G) denote the minimum cardinality of a connected dominating set for G. A graph G is k-γ c -critical if γ c (G) = k, but γ c (G + xy) < k for xy Î E([`(G)])xyE(G) . Further, for integer r ≥ 2, G is said to be k-(γ c , r)-critical if γ c (G) = k, but γ c (G + xy) < k for each pair of non-adjacent vertices x and y that are at distance at most r apart. k-γ c -critical graphs are k-(γ c , r)-critical but the converse need not be true. In this paper, we give a characterization of 3-(γ c , 2)-critical claw-free graphs which are not 3-γ c -critical. In fact, we show that there are exactly four classes of such graphs. 2010 Journal Article http://hdl.handle.net/20.500.11937/19085 10.1007/s00373-010-0920-2 Springer Japan KK restricted |
| spellingShingle | Critical graph Connected domination Claw-free Ananchuen, Watcharaphong Ananchuen, Nawarat Caccetta, Louis A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical |
| title | A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical |
| title_full | A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical |
| title_fullStr | A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical |
| title_full_unstemmed | A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical |
| title_short | A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical |
| title_sort | characterization of 3-(γc, 2)-critical claw-free graphs which are not 3-γc-critical |
| topic | Critical graph Connected domination Claw-free |
| url | http://hdl.handle.net/20.500.11937/19085 |