Advanced Search

Let $e_{ij}$ be the number of edges in a convex 3-polytope joining the vertices of degree i with the vertices of degree j. We prove that for every convex 3-polytope there is $20e_{3,3}+25e_{3,4}+16e_{3,5}+10e_{3,6}+6[2/3]e_{3,7}+5e_{3,8}+2[1/2]e_{3,9}+2e_{3,10}+16[2/3]e_{4,4}+11e_{4,5}+5e_{4,6}+1[2/3]e_{4,7}+5[1/3]e_{5,5}+2e_{5,6}\ge 120$; moreover, each coefficient is the best possible. This result brings a final answer to the conjecture raised by B. Grünbaum in 1973.

A unique-maximum k-coloring with respect to faces of a plane graph G is a coloring with colors 1, . . . , k so that, for each face of G, the maximum color occurs exactly once on the vertices of α. We prove that any plane graph is unique-maximum 3-colorable and has a proper unique-maximum coloring with 6 colors.

A nonempty vertex set X ⊆ V (G) of a hamiltonian graph G is called an H-force set of G if every X-cycle of G (i.e. a cycle of G containing all vertices of X) is hamiltonian. The H-force number h(G) of a graph G is defined to be the smallest cardinality of an H-force set of G. In the paper the study of this parameter is introduced and its value or a lower bound for outerplanar graphs, planar graphs, k-connected graphs and prisms over graphs is determined.

The existence of paths of low degree sum of their vertices in planar graphs is investigated. The main results of the paper are: 1. Every 3-connected simple planar graph G that contains a k-path, a path on k vertices, also contains a k-path P such that for its weight (the sum of degrees of its vertices) in G it holds $w_G\left(P\right):={\sum }_{u\in V\left(P\right)}de{g}_G\left(u\right)\le (3/2)k²+\left(k\right)$ 2. Every plane triangulation T that contains a k-path also contains a k-path P such that for its weight in T it holds $w_T\left(P\right):={\sum }_{u\in V\left(P\right)}de{g}_T\left(u\right)\le k²+13k$ 3. Let G be a 3-connected simple planar graph of circumference...

A planar 3-connected graph G is essentially 4-connected if, for any 3-separator S of G, one component of the graph obtained from G by removing S is a single vertex. Jackson and Wormald proved that an essentially 4-connected planar graph on n vertices contains a cycle C such that [...] . For a cubic essentially 4-connected planar graph G, Grünbaum with Malkevitch, and Zhang showed that G has a cycle on at least ¾ n vertices. In the present paper the result of Jackson and Wormald is improved. Moreover,...