Geodesic
Partitioning Harary graphs into connected subgraphs containing prescribed vertices
Discrete mathematics & theoretical computer science, Tome 16 (2014) no. 3.

Voir la notice de l'article provenant de la source Episciences

A graph G is arbitrarily partitionable (AP for short) if for every partition (n_1, n_2, ..., n_p) of |V(G)| there exists a partition (V_1, V_2, ..., V_p) of V(G) such that each V_i induces a connected subgraph of G with order n_i. If, additionally, k of these subgraphs (k <= p) each contains an arbitrary vertex of G prescribed beforehand, then G is arbitrarily partitionable under k prescriptions (AP+k for short). Every AP+k graph on n vertices is (k+1)-connected, and thus has at least ceil(n(k+1)/2) edges. We show that there exist AP+k graphs on n vertices and ceil(n(k+1)/2) edges for every k >= 1 and n >= k. 
@article{DMTCS_2014_16_3_a0,
     author = {Baudon, Olivier and Bensmail, Julien and Sopena, Eric},
     title = {Partitioning {Harary} graphs into connected subgraphs containing prescribed vertices},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {16},
     number = {3},
     year = {2014},
     doi = {10.46298/dmtcs.641},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.641/}
}
TY  - JOUR
AU  - Baudon, Olivier
AU  - Bensmail, Julien
AU  - Sopena, Eric
TI  - Partitioning Harary graphs into connected subgraphs containing prescribed vertices
JO  - Discrete mathematics & theoretical computer science
PY  - 2014
VL  - 16
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.641/
DO  - 10.46298/dmtcs.641
LA  - en
ID  - DMTCS_2014_16_3_a0
ER  - 
%0 Journal Article
%A Baudon, Olivier
%A Bensmail, Julien
%A Sopena, Eric
%T Partitioning Harary graphs into connected subgraphs containing prescribed vertices
%J Discrete mathematics & theoretical computer science
%D 2014
%V 16
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.641/
%R 10.46298/dmtcs.641
%G en
%F DMTCS_2014_16_3_a0
Baudon, Olivier; Bensmail, Julien; Sopena, Eric. Partitioning Harary graphs into connected subgraphs containing prescribed vertices. Discrete mathematics & theoretical computer science, Tome 16 (2014) no. 3. doi : 10.46298/dmtcs.641. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.641/

Cité par Sources :