Geodesic
Cores of vertex transitive graphs
David E. Roberson1
1University of Waterloo
The electronic journal of combinatorics, Tome 20 (2013) no. 2
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A core of a graph X is a vertex minimal subgraph to which X admits a homomorphism. Hahn and Tardif have shown that for vertex transitive graphs, the size of the core must divide the size of the graph. This motivates the following question: when can the vertex set of a vertex transitive graph be partitioned into sets each of which induce a copy of its core? We show that normal Cayley graphs and vertex transitive graphs with cores half their size always admit such partitions. We also show that the vertex sets of vertex transitive graphs with cores less than half their size do not, in general, have such partitions.
DOI : 10.37236/3144
Classification : 05C60, 05C70, 05C25
Mots-clés : core of a graph, vertex minimal subgraph, graph homomorphisms, vertex transitive graphs

David E. Roberson  1

1 University of Waterloo 
@article{10_37236_3144,
     author = {David E. Roberson},
     title = {Cores of vertex transitive graphs},
     journal = {The electronic journal of combinatorics},
     year = {2013},
     volume = {20},
     number = {2},
     doi = {10.37236/3144},
     zbl = {1266.05100},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/3144/}
}
TY  - JOUR
AU  - David E. Roberson
TI  - Cores of vertex transitive graphs
JO  - The electronic journal of combinatorics
PY  - 2013
VL  - 20
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.37236/3144/
DO  - 10.37236/3144
ID  - 10_37236_3144
ER  - 
%0 Journal Article
%A David E. Roberson
%T Cores of vertex transitive graphs
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/3144/
%R 10.37236/3144
%F 10_37236_3144
David E. Roberson. Cores of vertex transitive graphs. The electronic journal of combinatorics, Tome 20 (2013) no. 2. doi: 10.37236/3144

Cité par Sources :