Geodesic
Clusters in a multigraph with elevated density
The electronic journal of combinatorics, Tome 14 (2007)

Voir la notice de l'article provenant de la source The Electronic Journal of Combinatorics website

Zbl EuDML
In this paper, we prove that in a multigraph whose density $\Gamma$ exceeds the maxiimum vertex degree $\Delta$, the collection of minimal clusters (maximally dense sets of vertices) is cycle-free. We also prove that for multigraphs with $\Gamma\gt\Delta+1$, the size of any cluster is bounded from the above by $(\Gamma-3)/(\Gamma-\Delta-1)$. Finally, we show that two well-known lower bounds for the chromatic index of a multigraph are equal.
DOI : 10.37236/4847
Classification : 05C15, 05C35 
Mark K. Goldberg. Clusters in a multigraph with elevated density. The electronic journal of combinatorics, Tome 14 (2007). doi: 10.37236/4847
@article{10_37236_4847,
     author = {Mark K. Goldberg},
     title = {Clusters in a multigraph with elevated density},
     journal = {The electronic journal of combinatorics},
     year = {2007},
     volume = {14},
     doi = {10.37236/4847},
     zbl = {1110.05032},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/4847/}
}
TY  - JOUR
AU  - Mark K. Goldberg
TI  - Clusters in a multigraph with elevated density
JO  - The electronic journal of combinatorics
PY  - 2007
VL  - 14
UR  - http://geodesic.mathdoc.fr/articles/10.37236/4847/
DO  - 10.37236/4847
ID  - 10_37236_4847
ER  - 
%0 Journal Article
%A Mark K. Goldberg
%T Clusters in a multigraph with elevated density
%J The electronic journal of combinatorics
%D 2007
%V 14
%U http://geodesic.mathdoc.fr/articles/10.37236/4847/
%R 10.37236/4847
%F 10_37236_4847

Cité par Sources :