×

Vertex-pancyclism in the generalized sum of digraphs. (English) Zbl 1460.05074

Summary: A digraph \(D = ( V ( D ) , A ( D ) )\) of order \(n \geq 3\) is pancyclic, whenever \(D\) contains a directed cycle of length \(k\) for each \(k \in \{ 3 , \ldots , n \} \); and \(D\) is vertex-pancyclic iff, for each vertex \(v \in V ( D )\) and each \(k \in \{ 3 , \ldots , n \}\), \(D\) contains a directed cycle of length \(k\) passing through \(v\).
Let \(D_1, D_2, \dots, D_k\) be a collection of pairwise vertex disjoint digraphs. The generalized sum (g.s.) of \(D_1, D_2, \dots, D_k\), denoted by \(\oplus_{i = 1}^k D_i\) or \(D_1 \oplus D_2 \oplus \cdots \oplus D_k\), is the set of all digraphs \(D\) satisfying: (i) \( V ( D ) = \bigcup_{i = 1}^k V ( D_i )\), (ii) \( D \langle V ( D_i ) \rangle \cong D_i\) for \(i = 1 , 2 , \ldots , k\), and (iii) for each pair of vertices belonging to different summands of \(D\), there is exactly one arc between them, with an arbitrary but fixed direction. A digraph \(D\) in \(\oplus_{i = 1}^k D_i\) will be called a generalized sum (g.s.) of \(D_1, D_2, \dots, D_k\).
Let \(D_1, D_2, \dots, D_k\) be a collection of \(k\) pairwise vertex disjoint Hamiltonian digraphs, in this paper we give simple sufficient conditions for a digraph \(D \in \oplus_{i = 1}^k D_i\) to be vertex-pancyclic. This result extends a result obtained by N. Cordero-Michel et al. [Discrete Math. 339, No. 6, 1763–1770 (2016; Zbl 1333.05135)].

MSC:

05C20 Directed graphs (digraphs), tournaments
05C38 Paths and cycles
05C12 Distance in graphs

Citations:

Zbl 1333.05135
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Bang-Jensen, J.; Guo, Y., A note on vertex pancyclic oriented graphs, J. Graph Theory, 31, 313-318 (1999) · Zbl 0944.05061
[2] Bang-Jensen, J.; Gutin, G., (Digraphs: Theory, Algorithms and Applications. Digraphs: Theory, Algorithms and Applications, Springer Monographs in Mathematics (2009), Springer-Verlag London, Ltd: Springer-Verlag London, Ltd London) · Zbl 1170.05002
[3] Bang-Jensen, J.; Huang, J., Quasi-transitive digraphs, J. Graph Theory, 20, 2, 141-161 (1995) · Zbl 0832.05048
[4] Cordero-Michel, N.; Galeana-Sánchez, H., Vertex alternating-pancyclism in 2-edge-colored generalized sums of graphs, Discrete Appl. Math. (2020) · Zbl 1443.05062
[5] Cordero-Michel, N.; Galeana-Sánchez, H.; Goldfeder, I., Some results on the existence of hamiltonian cycles in the generalized sum of digraphs, Discrete Math., 339, 1763-1770 (2016) · Zbl 1333.05135
[6] Galeana-Sánchez, H.; Goldfeder, I., Hamiltonian cycles in a generalization of bipartite tournaments with a cycle-factor, Discrete Math., 315-316, 135-143 (2014) · Zbl 1279.05043
[7] Gutin, G., Characterizations of vertex pancyclic and pancyclic ordinary complete multipartite digraphs, Discrete Math., 141, 1-3, 153-162 (1995) · Zbl 0839.05042
[8] Li, H.; Li, S.; Guo, Y.; Surmacs, M., On the vertex-pancyclicity of hypertournaments, Discrete Appl. Math., 161, 16-17, 2749-2752 (2013) · Zbl 1285.05079
[9] Moon, J., On subtournaments of a tournament, Canad. Math. Bull., 9, 297-301 (1966) · Zbl 0141.41204
[10] Randerath, B.; Schiermeyer, I.; Tewes, M.; Volkmann, L., Vertex pancyclic graphs, Discrete Appl. Math., 120, 1-3, 219-237 (2002) · Zbl 1001.05070
[11] Thomassen, C., An ore-type condition implying a digraph to be pancyclic, Discrete Math., 19, 1, 85-92 (1977) · Zbl 0361.05034
[12] Yeo, A., Diregular \(c\)-partite tournaments are vertex-pancyclic when \(c \geq 5\), J. Graph Theory, 32, 137-152 (1999) · Zbl 0931.05037
[13] Yeo, A., Paths and cycles containing given arcs, in close to regular multipartite tournaments, J. Graph Theory Ser. B, 97, 6, 949-963 (2007) · Zbl 1124.05053
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.