The choice number of a graph G is the smallest integer k such that for every assignment of a list L(v) of k colors to each vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from L(v). We present upper and lower bounds on the choice number of complete multipartite graphs with partite classes of equal sizes and complete r-partite graphs with r-1 partite classes of order two.
2
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
The Gutman index and the edge-Wiener index have been extensively investigated particularly in the last decade. An important stream of re- search on graph indices is to bound indices in terms of the order and other parameters of given graph. In this paper we present asymptotically sharp upper bounds on the Gutman index and the edge-Wiener index for graphs of given order and vertex-connectivity κ, where κ is a constant. Our results substantially generalize and extend known results in the area.
3
Dostęp do pełnego tekstu na zewnętrznej witrynie WWW
For positive integers Δ and D we define nΔ,D to be the largest number of vertices in an outerplanar graph of given maximum degree Δ and diameter D. We prove that [...] nΔ,D=ΔD2+O (ΔD2−1) $n_{\Delta ,D} = \Delta ^{{D \over 2}} + O\left( {\Delta ^{{D \over 2} - 1} } \right)$ is even, and [...] nΔ,D=3ΔD−12+O (ΔD−12−1) $n_{\Delta ,D} = 3\Delta ^{{{D - 1} \over 2}} + O\left( {\Delta ^{{{D - 1} \over 2} - 1} } \right)$ if D is odd. We then extend our result to maximal outerplanar graphs by showing that the maximum number of vertices in a maximal outerplanar graph of maximum degree Δ and diameter D asymptotically equals nΔ,D.
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.