Show simple item record

dc.contributor.authorAnanchuen, Watcharaphong
dc.contributor.authorAnanchuen, Nawarat
dc.contributor.authorCaccetta, Louis
dc.date.accessioned2017-01-30T12:11:50Z
dc.date.available2017-01-30T12:11:50Z
dc.date.created2011-03-23T20:01:27Z
dc.date.issued2010
dc.identifier.citationAnanchuen, Watcharaphong and Ananchuen, Nawarat and Caccetta, Louis. 2010. A Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical. Graphs and Combinatorics. 26 (3): pp. 315-328.
dc.identifier.urihttp://hdl.handle.net/20.500.11937/19085
dc.identifier.doi10.1007/s00373-010-0920-2
dc.description.abstract

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.

dc.publisherSpringer Japan KK
dc.subjectCritical graph
dc.subjectConnected domination
dc.subjectClaw-free
dc.titleA Characterization of 3-(γc, 2)-Critical Claw-Free Graphs Which are not 3-γc-Critical
dc.typeJournal Article
dcterms.source.volume26
dcterms.source.startPage315
dcterms.source.endPage328
dcterms.source.issn0911-0119
dcterms.source.titleGraphs and Combinatorics
curtin.departmentDepartment of Mathematics and Statistics
curtin.accessStatusFulltext not available


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record