File Download
  Links for fulltext
     (May Require Subscription)
Supplementary

Article: A characterization of almost CIS graphs

TitleA characterization of almost CIS graphs
Authors
KeywordsAlgorithm
Clique
Graph
Stable set
Issue Date2009
PublisherSociety for Industrial and Applied Mathematics. The Journal's web site is located at http://epubs.siam.org/sam-bin/dbq/toclist/SIDMA
Citation
SIAM Journal On Discrete Mathematics, 2009, v. 23 n. 2, p. 749-753 How to Cite?
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
2015 Impact Factor: 0.793
2015 SCImago Journal Rankings: 1.230
ISI Accession Number ID
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

 

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://epubs.siam.org/sam-bin/dbq/toclist/SIDMAen_HK
dc.relation.ispartofSIAM Journal on Discrete Mathematicsen_HK
dc.rightsCreative Commons: Attribution 3.0 Hong Kong License-
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.openurlhttp://library.hku.hk:4550/resserv?sid=HKU:IR&issn=0859-4801&volume=23&spage=749&epage=753&date=2009&atitle=A+Characterization+of+Almost+CIS+Graphsen_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

Export via OAI-PMH Interface in XML Formats


OR


Export to Other Non-XML Formats