Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-25T14:03:01.365Z Has data issue: false hasContentIssue false
  • English
  • Français

Path node-covering constants for certain families of trees

Published online by Cambridge University Press:  24 October 2008

A. Meir  and
J. W. Moon
A. Meir
Affiliation:
University of Alberta, EdmontonUniversity of the WitwatersrandJohannesburg
J. W. Moon
Affiliation:
University of Alberta, EdmontonUniversity of the WitwatersrandJohannesburg
Get access Rights & Permissions [Opens in a new window]

Extract

1. introduction. A set P of disjoint paths in a graph G is a node-covering of G if every node of G is in a path in P. (For definitions not given here see (5) or (11).) The path (node-covering) number of G is the smallest possible number p(G) of paths in such a node-covering of G. The problem of determining the path number of a graph was considered in (1) and (4) for undirected graphs and in (2) for directed graphs. In particular, an algorithm for determining the path number of a tree was given in (1) and (4). If ℱ denotes some family of trees, let μ(n) = μℱ(n) denote the average value of p(T) over all trees T in ℱ with n nodes. Our object here is to show the existence and to determine the value of the path (node-covering) constant

for certain families ℱ of trees. The arguments are similar to those used in (7), (8), and (9), where some other parameters, associated with families of trees, were investigated.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 84 , Issue 3 , November 1978 , pp. 519 - 530
Copyright
Copyright © Cambridge Philosophical Society 1978

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

(1)Boesch, F. T., Chen, S. and Mchugh, J. A. M. On covering the points of a graph with point disjoint paths. In Proc. 1973 Capital conference on graph theory and combinatorics, ed. Bari, R. A. and Harary, F. (New York, Springer-Verlag, 1974), pp. 201–212.Google Scholar
(2)Boesch, F. T. and Gimpel, J. F.Covering the points of a digraph with point disjoint paths and its application to code optimization. J. Assoc. Comput. Mach. 24 (1977), 192–195.Google Scholar
(3)Cayley, A.On the analytical forms called trees. Philos. Mag. 28 (1858), 374–378. (Collected Mathematical Papers, Cambridge, 4 (1891), 112–115.)Google Scholar
(4)Goodman, S. and Hedetntemi, S. T. On the hamiltonian completion problem. Proc. 1973 Capital conference on graph theory and combinatorics, ed. Bari, R. A. and Harary, F. (New York, Springer–Verlag, 1974), pp. 262–272.Google Scholar
(5)Harary, F. and Palmer, E.Graphical enumeration (New York, Academic Press, 1973).Google Scholar
(6)Meir, A. and Moon, J. W. The expected node-independence number of various types of trees. In Recent advances in graph theory, ed. Fiedler, M. (Academia Praha, 1975), pp. 351–363.Google Scholar
(7)Meir, A. and Moon, J. W.Packing and covering constants for certain families of trees: I. J. Graph Theory 1 (1977), 157–174.Google Scholar
(8)Meir, A. and Moon, J. W.Packing and covering constants for certain families of trees: II. Trans. Amer. Math. Soc. 233 (1977), 167–178.Google Scholar
(9)Meir, A. and Moon, J. W. Packing and covering constants for recursive trees. In Proc. International Conference on Graph Theory at Western Michigan University, 1976 (New York, Springer-Verlag, to appear).Google Scholar
(10)Meir, A. and Moon, J. W.On the altitude of nodes in certain families of trees. Canad. J. Math.Google Scholar
(11)Moon, J. W.Counting labelled trees (Canadian Mathematical Congress, Montreal, 1970).Google Scholar
(12)Otter, R.The number of trees. Ann. of Math. 49 (1948), 583–599.Google Scholar
(13)Pólya, G.Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen. Acta Math. 68 (1937), 145–254.Google Scholar