On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs.
Farrell, E.J. (1983)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Displaying similar documents to “The Orderly Colored Longest Path Problem – a survey of applications and new algorithms”
On a class of polynomials associated with the paths in a graph and its application to minimum nodes disjoint path coverings of graphs.
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
Similarity:
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...
Subgraph densities in signed graphons and the local Simonovits-Sidorenko conjecture.
Lovász, László (2011)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
On coefficients of path polynomials.
Farrell, E.J. (1984)
International Journal of Mathematics and Mathematical Sciences
Similarity:
Methods of destroying the symmetries of a graph.
Harary, Frank (2001)
Bulletin of the Malaysian Mathematical Sciences Society. Second Series
Similarity:
On k-Path Pancyclic Graphs
Zhenming Bi, Ping Zhang (2015)
Discussiones Mathematicae Graph Theory
Similarity:
For integers k and n with 2 ≤ k ≤ n − 1, a graph G of order n is k-path pancyclic if every path P of order k in G lies on a cycle of every length from k + 1 to n. Thus a 2-path pancyclic graph is edge-pancyclic. In this paper, we present sufficient conditions for graphs to be k-path pancyclic. For a graph G of order n ≥ 3, we establish sharp lower bounds in terms of n and k for (a) the minimum degree of G, (b) the minimum degree-sum of nonadjacent vertices of G and (c) the size of G...
Note on linear arboricity
Pavel Tomasta (1982)
Mathematica Slovaca
Similarity:
More on the complexity of cover graphs
Jaroslav Nešetřil, Vojtěch Rödl (1995)
Commentationes Mathematicae Universitatis Carolinae
Similarity:
In response to [3] and [4] we prove that the recognition of cover graphs of finite posets is an NP-hard problem.
Glossary of signed and gain graphs and allied areas.
Zaslavsky, Thomas (1998)
The Electronic Journal of Combinatorics [electronic only]
Similarity:
Characterizations of Graphs Having Large Proper Connection Numbers
Chira Lumduanhom, Elliot Laforge, Ping Zhang (2016)
Discussiones Mathematicae Graph Theory
Similarity:
Let G be an edge-colored connected graph. A path P is a proper path in G if no two adjacent edges of P are colored the same. If P is a proper u − v path of length d(u, v), then P is a proper u − v geodesic. An edge coloring c is a proper-path coloring of a connected graph G if every pair u, v of distinct vertices of G are connected by a proper u − v path in G, and c is a strong proper-path coloring if every two vertices u and v are connected by a proper u− v geodesic in G. The minimum...