Light paths with an odd number of vertices in polyhedral maps

Stanislav Jendroľ; Heinz-Jürgen Voss

Displaying similar documents to “Light paths with an odd number of vertices in polyhedral maps”

Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ (1999)

Czechoslovak Mathematical Journal

Similarity:

In this paper it is proved that every $3$ -connected planar graph contains a path on $3$ vertices each of which is of degree at most $15$ and a path on $4$ vertices each of which has degree at most $23$ . Analogous results are stated for $3$ -connected planar graphs of minimum degree $4$ and $5$ . Moreover, for every pair of integers $n \geq 3$ , $k \geq 4$ there is a $2$ -connected planar graph such that every path on $n$ vertices in it has a vertex of degree $k$ .

Classifying trees with edge-deleted central appendage number 2

Shubhangi Stalder, Linda Eroh, John Koker, Hosien S. Moghadam, Steven J. Winters (2009)

Mathematica Bohemica

Similarity:

The eccentricity of a vertex $v$ of a connected graph $G$ is the distance from $v$ to a vertex farthest from $v$ in $G$ . The center of $G$ is the subgraph of $G$ induced by the vertices having minimum eccentricity. For a vertex $v$ in a 2-edge-connected graph $G$ , the edge-deleted eccentricity of $v$ is defined to be the maximum eccentricity of $v$ in $G - e$ over all edges $e$ of $G$ . The edge-deleted center of $G$ is the subgraph induced by those vertices of $G$ having minimum edge-deleted eccentricity. The edge-deleted...

Light classes of generalized stars in polyhedral maps on surfaces

Stanislav Jendrol&#039;, Heinz-Jürgen Voss (2004)

Discussiones Mathematicae Graph Theory

Similarity:

A generalized s-star, s ≥ 1, is a tree with a root Z of degree s; all other vertices have degree ≤ 2. $S_{i}$ denotes a generalized 3-star, all three maximal paths starting in Z have exactly i+1 vertices (including Z). Let be a surface of Euler characteristic χ() ≤ 0, and m():= ⎣(5 + √49-24χ( ))/2⎦. We prove: (1) Let k ≥ 1, d ≥ m() be integers. Each polyhedral map G on with a k-path (on k vertices) contains a k-path of maximum degree ≤ d in G or a generalized s-star T, s ≤ m(), on d + 2- m()...

Vertex-disjoint stars in graphs

Katsuhiro Ota (2001)

Discussiones Mathematicae Graph Theory

Similarity:

In this paper, we give a sufficient condition for a graph to contain vertex-disjoint stars of a given size. It is proved that if the minimum degree of the graph is at least k+t-1 and the order is at least (t+1)k + O(t²), then the graph contains k vertex-disjoint copies of a star $K_{1, t}$ . The condition on the minimum degree is sharp, and there is an example showing that the term O(t²) for the number of uncovered vertices is necessary in a sense.

Bounds concerning the alliance number

Grady Bullington, Linda Eroh, Steven J. Winters (2009)

Mathematica Bohemica

Similarity:

P. Kristiansen, S. M. Hedetniemi, and S. T. Hedetniemi, in Alliances in graphs, J. Combin. Math. Combin. Comput. 48 (2004), 157–177, and T. W. Haynes, S. T. Hedetniemi, and M. A. Henning, in Global defensive alliances in graphs, Electron. J. Combin. 10 (2003), introduced the defensive alliance number $a (G)$ , strong defensive alliance number $\hat{a} (G)$ , and global defensive alliance number $γ_{a} (G)$ . In this paper, we consider relationships between these parameters and the domination number $γ (G)$ . For any positive...