×

zbMATH — the first resource for mathematics

Factors in a class of regular digraphs. (English) Zbl 0589.05038
For the class of 1-regular digraphs, the paper gives a simple closed form expression for the number of directed factors, shows a close relationship between the permanent and determinant of their adjacency matrices, and presents a necessary and sufficient condition for the Cartesian product of two directed circuits to have directed factor with exactly k components, thereby generalizing a result of Trotter and Erdős. The paper also shows that a conjecture of Bondy regarding vertex-transitive graphs fails to hold for vertex-transitive digraphs.
Reviewer: W.-K.Chen
MSC:
05C20 Directed graphs (digraphs), tournaments
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Hamiltonian graphs, in Selected Topics in Graph Theory ( and , Eds.), Academic, New York (1978) 127–167.
[2] Algebraic Graph Theory, Cambridge Tracts No. 67. Cambridge Univ. Press, London (1974). · Zbl 0797.05032 · doi:10.1017/CBO9780511608704
[3] Hamiltonian cycles in graphs and digraphs, Proc. 9th S-E Conf. Combinatorics, Graph Theory and Computing (1979) 3–28.
[4] Graph Theory: An Algorithmic Approach, Academic, New York (1975). · Zbl 0321.94011
[5] Graph Algorithms. Computer Science Press, Rockville, MD (1979).
[6] and , Computers and Intractability, Freeman, San Francisco (1979).
[7] Graph Theory, Addison-Wesley, Reading, MA (1969).
[8] Permanents, in Encyclopedia of Mathematics and its Applications. Addison-Wesley, Reading, MA (1978).
[9] Plesník, Inf. Proc. Lett. 8 pp 199– (1979)
[10] Trotter, J. Graph Theory 2 pp 137– (1978)
[11] Valiant, Theoretical Comput. Sci. 8 pp 189– (1979)
[12] Graphs, Groups and Surfaces, American Elsevier, New York (1973) 21–33.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.