Geodesic
Uniformly dissociated graphs
Ars Mathematica Contemporanea, Tome 13 (2017) no. 2, pp. 293-306.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

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 subgraph 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.
DOI : 10.26493/1855-3974.1013.46a
Keywords: Dissociation number, well-covered graphs, girth, Moore graph, polarity graph 
@article{10_26493_1855_3974_1013_46a,
     author = {Bo\v{s}tjan Bre\v{s}ar and Bert L. Hartnell and Douglas F. Rall},
     title = {Uniformly dissociated graphs},
     journal = {Ars Mathematica Contemporanea},
     pages = {293--306},
     publisher = {mathdoc},
     volume = {13},
     number = {2},
     year = {2017},
     doi = {10.26493/1855-3974.1013.46a},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1013.46a/}
}
TY  - JOUR
AU  - Boštjan Brešar
AU  - Bert L. Hartnell
AU  - Douglas F. Rall
TI  - Uniformly dissociated graphs
JO  - Ars Mathematica Contemporanea
PY  - 2017
SP  - 293
EP  - 306
VL  - 13
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1013.46a/
DO  - 10.26493/1855-3974.1013.46a
LA  - en
ID  - 10_26493_1855_3974_1013_46a
ER  - 
%0 Journal Article
%A Boštjan Brešar
%A Bert L. Hartnell
%A Douglas F. Rall
%T Uniformly dissociated graphs
%J Ars Mathematica Contemporanea
%D 2017
%P 293-306
%V 13
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1013.46a/
%R 10.26493/1855-3974.1013.46a
%G en
%F 10_26493_1855_3974_1013_46a
Boštjan Brešar; Bert L. Hartnell; Douglas F. Rall. Uniformly dissociated graphs. Ars Mathematica Contemporanea, Tome 13 (2017) no. 2, pp. 293-306. doi : 10.26493/1855-3974.1013.46a. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.1013.46a/

Cité par Sources :