Evènement pour le groupe GT Graphes et Applications


Date 2015-10-02  14:00-15:00
TitreLight structures in sparse graphs with minimum degree 2 
RésuméA graph $H$ is defined to be light in a graph family ${cal{G}}$ if there exists finite number $w(H,{cal{G}})$ such that each $G in {cal{G}}$ which contains $H$ as a subgraph, also contains its isomorphic copy $K$ with $sumlimits_{x in V(K)} deg_G(x) leq w(H,{cal{G}})$. In this talk we will investigate light short paths in families of graphs with bounded average degree and light structures in families of plane graphs of minimum degree 2 with prescribed girth. We will show that every graph with minimum degree at least 2 and average degree $ad (G) < frac{14}{5}$ and every plane graph with minimum degree at least 2 and girth $g(G) geq 7$ contains a light path on three vertices. Moreover we will give examples providing sharp bounds on $w(P_3)$ for families of graphs with prescribed $ad(G)$ or $g(G)$, respectively. Further we will show that graph $K_{1,3}$ is light in the family of plane graphs of girth $g(G) geq 7$, with $delta(G) geq 2$ and without adjacent 2-vertices, and $C_{10}$ is light in family of plane graphs of girth $g(G)=10$, with $delta(G) geq 2$ and without adjacent 2-vertices.  
LieuSalle 178 
OrateurRoman Soták 



Aucun document lié à cet événement.

Retour
Retour à l'index