Name
Abstract | ||
|---|---|---|
Let (G, w) denote a simple graph G with a weight function w: E(G) --> {0,1,2}. A path cover of (G, w) is a collection of paths in G such that every edge e is contained in exactly w(e) paths of the collection. For a vertex upsilon, w(upsilon) is the sum of the weights of the edges incident with upsilon;upsilon is called an odd (even) vertex if w(upsilon) is odd (even). We prove that if every vertex of (G, w) is incident with at most one edge of weight 2, then (G, w) has a path cover P such that each odd vertex occurs exactly once, and each even vertex exactly twice, as an end of a path of P. We also prove that if every vertex of (G, w) is even, then (G, w) has a path cover P such that each vertex occurs exactly twice as an end of a path of P. (C) 1995 John Wiley & Sons, Inc. |
Year | DOI | Venue |
|---|---|---|
1995 | 10.1002/jgt.3190190114 | Journal of Graph Theory |
Keywords | Field | DocType |
weighted graph | Discrete mathematics,Combinatorics,Weight function,Bound graph,Vertex (geometry),Vertex (graph theory),Neighbourhood (graph theory),Shortest-path tree,Path cover,Mathematics,Saturation (graph theory) | Journal |
Volume | Issue | ISSN |
19 | 1 | 0364-9024 |
Citations | PageRank | References |
1 | 0.35 | 0 |
Authors | ||
1 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Genghua Fan | 1 | 412 | 65.22 |