All a b c d e f g h i j k l m n o p q r s t u v w x y z Other

Previous Page 21 Next

Displaying 401 – 420 of 513

Showing per page

Paths of low weight in planar graphs

Igor Fabrici, Jochen Harant, Stanislav Jendrol' (2008)

Discussiones Mathematicae Graph Theory

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 ( P ) : = ∑ u ∈ V ( P ) d e g G ( u ) ≤ ( 3 / 2 ) k ² + ( k ) 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 ( P ) : = ∑ u ∈ V ( P ) d e g T ( u ) ≤ k ² + 13 k 3. Let G be a 3-connected simple planar graph of circumference...

Paths through fixed vertices in edge-colored graphs

W. S. Chou, Y. Manoussakis, O. Megalakaki, M. Spyratos, Zs. Tuza (1994)

Mathématiques et Sciences Humaines

We study the problem of finding an alternating path having given endpoints and passing through a given set of vertices in edge-colored graphs (a path is alternating if any two consecutive edges are in different colors). In particular, we show that this problem in NP-complete for 2-edge-colored graphs. Then we give a polynomial characterization when we restrict ourselves to 2-edge-colored complete graphs. We also investigate on (s,t)-paths through fixed vertices, i.e. paths of length s+t such that...

Paths with restricted degrees of their vertices in planar graphs

Stanislav Jendroľ (1999)

Czechoslovak Mathematical Journal

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 ≥ 3 , k ≥ 4 there is a 2 -connected planar graph such that every path on n vertices in it has a vertex of degree k .

Rainbow connection in graphs

Gary Chartrand, Garry L. Johns, Kathleen A. McKeon, Ping Zhang (2008)

Mathematica Bohemica

Let G be a nontrivial connected graph on which is defined a coloring c E ( G ) → { 1 , 2 , ... , k } , k ∈ ℕ , of the edges of G , where adjacent edges may be colored the same. A path P in G is a rainbow path if no two edges of P are colored the same. The graph G is rainbow-connected if G contains a rainbow u - v path for every two vertices u and v of G . The minimum k for which there exists such a k -edge coloring is the rainbow connection number r c ( G ) of G . If for every pair u , v of distinct vertices, G contains a rainbow u - v geodesic, then G is...

Randomly H graphs

Gary Chartrand, Ortrud R. Oellermann, Sergio Ruiz (1986)

Mathematica Slovaca

Relations between ( κ , τ ) -regular sets and star complements

Milica Anđelić, Domingos M. Cardoso, Slobodan K. Simić (2013)

Czechoslovak Mathematical Journal

Let G be a finite graph with an eigenvalue μ of multiplicity m . A set X of m vertices in G is called a star set for μ in G if μ is not an eigenvalue of the star complement G ∖ X which is the subgraph of G induced by vertices not in X . A vertex subset of a graph is ( κ , τ ) -regular if it induces a κ -regular subgraph and every vertex not in the subset has τ neighbors in it. We investigate the graphs having a ( κ , τ ) -regular set which induces a star complement for some eigenvalue. A survey of known results is provided...

Currently displaying 401 – 420 of 513