Factors in a class of regular digraphs.

*(English)*Zbl 0589.05038For 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.) |

##### Keywords:

regular digraphs; directed factors; permanent; determinant; adjacency matrices; Cartesian product; directed circuits
PDF
BibTeX
XML
Cite

\textit{M. V. S. Ramanath}, J. Graph Theory 9, No. 1, 161--175 (1985; Zbl 0589.05038)

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.