File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A characterization of almost CIS graphs

TitleA characterization of almost CIS graphs
Authors
Wu, YZang, WZhang, CQ
KeywordsAlgorithm
Clique
Graph
Stable set
Issue Date2009
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php
Citation
SIAM Journal On Discrete Mathematics, 2009, v. 23 n. 2, p. 749-753 How to Cite?
DOI: http://dx.doi.org/10.1137/080723739
AbstractAgraph G is called CIS if each maximal clique intersects each maximal stable set in G and is called almost CIS if it has a unique disjoint pair (C, S) consisting of a maximal clique C and a maximal stable set S. While it is still unknown if there exists a good structural characterization of all CIS graphs, in this note we prove the following Andrade-Boros-Gurvich conjecture: A graph is almost CIS if and only if it is a split graph with a unique split partition. © 2009 Society for Industrial and Applied Mathematics.
Persistent Identifierhttp://hdl.handle.net/10722/58947
ISSN
0895-4801
2023 Impact Factor: 0.9
2023 SCImago Journal Rankings: 1.031
ISI Accession Number ID
WOS:000267744700013
Funding AgencyGrant Number
National Security AgencyMDA904-00-1-0061
MDA904-01-1-0022
Funding Information:

The third author was supported in part by the National Security Agency under grants MDA904-00-1-0061 and MDA904-01-1-0022.

References
References in Scopus

 

DC FieldValueLanguage
dc.contributor.authorWu, Yen_HK
dc.contributor.authorZang, Wen_HK
dc.contributor.authorZhang, CQen_HK
dc.date.accessioned2010-05-31T03:40:10Z-
dc.date.available2010-05-31T03:40:10Z-
dc.date.issued2009en_HK
dc.identifier.citationSIAM Journal On Discrete Mathematics, 2009, v. 23 n. 2, p. 749-753en_HK
dc.identifier.issn0895-4801en_HK
dc.identifier.urihttp://hdl.handle.net/10722/58947-
dc.description.abstractAgraph G is called CIS if each maximal clique intersects each maximal stable set in G and is called almost CIS if it has a unique disjoint pair (C, S) consisting of a maximal clique C and a maximal stable set S. While it is still unknown if there exists a good structural characterization of all CIS graphs, in this note we prove the following Andrade-Boros-Gurvich conjecture: A graph is almost CIS if and only if it is a split graph with a unique split partition. © 2009 Society for Industrial and Applied Mathematics.en_HK
dc.languageengen_HK
dc.publisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://www.siam.org/journals/sidma.php-
dc.relation.ispartofSIAM Journal on Discrete Mathematicsen_HK
dc.rights© 2009 Society for Industrial and Applied Mathematics. First Published in SIAM Journal on Discrete Mathematics in volume 23, issue 2, published by the Society for Industrial and Applied Mathematics (SIAM).-
dc.subjectAlgorithmen_HK
dc.subjectCliqueen_HK
dc.subjectGraphen_HK
dc.subjectStable seten_HK
dc.titleA characterization of almost CIS graphsen_HK
dc.typeArticleen_HK
dc.identifier.emailZang, W:wzang@maths.hku.hken_HK
dc.identifier.authorityZang, W=rp00839en_HK
dc.description.naturepublished_or_final_version-
dc.identifier.doi10.1137/080723739en_HK
dc.identifier.scopuseid_2-s2.0-73349122581en_HK
dc.identifier.hkuros162703en_HK
dc.relation.referenceshttp://www.scopus.com/mlt/select.url?eid=2-s2.0-73349122581&selection=ref&src=s&origin=recordpageen_HK
dc.identifier.volume23en_HK
dc.identifier.issue2en_HK
dc.identifier.spage749en_HK
dc.identifier.epage753en_HK
dc.identifier.isiWOS:000267744700013-
dc.publisher.placeUnited Statesen_HK
dc.identifier.scopusauthoridWu, Y=35187974700en_HK
dc.identifier.scopusauthoridZang, W=7005740804en_HK
dc.identifier.scopusauthoridZhang, CQ=7405492841en_HK
dc.identifier.issnl0895-4801-

Export via OAI-PMH Interface in XML Formats

OR

Export to Other Non-XML Formats