Uniformly dissociated graphs

Show simple item record

dc.creator Brešar, Boštjan
dc.creator Hartnell, Bert L.
dc.creator Rall, Douglas F.
dc.date.accessioned 2021-09-24T14:19:17Z
dc.date.available 2021-09-24T14:19:17Z
dc.date.issued 2017-03-09
dc.identifier.issn 1855-3974
dc.identifier.uri http://library2.smu.ca/xmlui/handle/01/29933
dc.description Creative Commons Attribution 3.0 International License en_CA
dc.description.abstract A set D of vertices in a graph G is called a dissociation set if every vertex in D has at most one neighbor in D. We call a graph G uniformly dissociated if all maximal dissociation sets are of the same cardinality. Characterizations of uniformly dissociated graphs with small cardinalities of dissociation sets are proven; in particular, the graphs in which all maximal dissociation sets are of cardinality 2 are the complete graphs on at least two vertices from which possibly a matching is removed, while the graphs in which all maximal dissociation sets are of cardinality 3 are the complements of the K4-free geodetic graphs with diameter 2. A general construction by which any graph can be embedded as an induced sub graph of a uniformly dissociated graph is also presented. In the main result we characterize uniformly dissociated graphs with girth at least 7 to be either isomorphic to C7, or obtainable from an arbitrary graph H with girth at least 7 by identifying each vertex of H with a leaf of a copy of P3. en_CA
dc.description.provenance Submitted by Sherry Briere (sherry.briere@smu.ca) on 2021-09-24T14:19:17Z No. of bitstreams: 1 Hartnell_Bert_L_article_2017.pdf: 331213 bytes, checksum: d31de2bdc9be3bbddf1b11ffff532e45 (MD5) en
dc.description.provenance Made available in DSpace on 2021-09-24T14:19:17Z (GMT). No. of bitstreams: 1 Hartnell_Bert_L_article_2017.pdf: 331213 bytes, checksum: d31de2bdc9be3bbddf1b11ffff532e45 (MD5) Previous issue date: 2017-03-09 en
dc.language.iso en en_CA
dc.publisher Attribution 3.0 International (CC BY 3.0) en_CA
dc.relation.uri https://doi.org/10.26493/1855-3974.1013.46a
dc.rights Creative Commons Attribution 3.0 International License
dc.title Uniformly dissociated graphs en_CA
dc.type Text en_CA
dcterms.bibliographicCitation Ars Mathematica Contemporanea 13(2), 293–306. (2017) en_CA
 Find Full text

Files in this item


 

Copyright statement:

 
Creative Commons Attribution 3.0 International License
 
Published Version: https://doi.org/10.26493/1855-3974.1013.46a
 
 

This item appears in the following Collection(s)

Show simple item record

Search DSpace


Browse

My Account