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 7 Next

Displaying 121 – 140 of 376

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 .

Pattern avoiding partitions and Motzkin left factors

Toufik Mansour, Mark Shattuck (2011)

Open Mathematics

Let L n, n ≥ 1, denote the sequence which counts the number of paths from the origin to the line x = n − 1 using (1, 1), (1, −1), and (1, 0) steps that never dip below the x-axis (called Motzkin left factors). The numbers L n count, among other things, certain restricted subsets of permutations and Catalan paths. In this paper, we provide new combinatorial interpretations for these numbers in terms of finite set partitions. In particular, we identify four classes of the partitions of size n, all...

Pattern hypergraphs.

Dvořák, Zdeněk, Kára, Jan, Král', Daniel, Pangrác, Ondřej (2010)

The Electronic Journal of Combinatorics [electronic only]

Pebblings.

Eriksson, Henrik (1995)

The Electronic Journal of Combinatorics [electronic only]

Pentadiagonal Companion Matrices

Brydon Eastman, Kevin N. Vander Meulen (2016)

Special Matrices

The class of sparse companion matrices was recently characterized in terms of unit Hessenberg matrices. We determine which sparse companion matrices have the lowest bandwidth, that is, we characterize which sparse companion matrices are permutationally similar to a pentadiagonal matrix and describe how to find the permutation involved. In the process, we determine which of the Fiedler companion matrices are permutationally similar to a pentadiagonal matrix. We also describe how to find a Fiedler...

Currently displaying 121 – 140 of 376