Back to Search
Start Over
Rainbow Triangles in Arc-Colored Tournaments
- Source :
- Graphs and Combinatorics. 37:1271-1290
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
Abstract
- Let $$T_{n}$$ be an arc-colored tournament of order n. The maximum monochromatic indegree $$\varDelta ^{-mon}(T_{n})$$ (resp. outdegree $$\varDelta ^{+mon}(T_{n})$$ ) of $$T_{n}$$ is the maximum number of in-arcs (resp. out-arcs) of a same color incident to a vertex of $$T_{n}$$ . The irregularity $$i(T_{n})$$ of $$T_{n}$$ is the maximum difference between the indegree and outdegree of a vertex of $$T_{n}$$ . A subdigraph H of an arc-colored digraph D is called rainbow if each pair of arcs in H have distinct colors. In this paper, we show that each vertex v in an arc-colored tournament $$T_{n}$$ with $$\varDelta ^{-mon}(T_n)\le \varDelta ^{+mon}(T_n)$$ is contained in at least $$\frac{\delta (v)(n-\delta (v)-i(T_n))}{2}-[\varDelta ^{-mon}(T_{n})(n-1)+\varDelta ^{+mon}(T_{n})d^+(v)]$$ rainbow triangles, where $$\delta (v)=\min \{d^+(v), d^-(v)\}$$ . We also give some maximum monochromatic degree conditions for $$T_{n}$$ to contain rainbow triangles, and to contain rainbow triangles passing through a given vertex. Finally, we present some examples showing that some of the conditions in our results are best possible.
- Subjects :
- Vertex (graph theory)
Mathematics::Combinatorics
Degree (graph theory)
0211 other engineering and technologies
Order (ring theory)
021107 urban & regional planning
Rainbow
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Theoretical Computer Science
Combinatorics
Computer Science::Discrete Mathematics
010201 computation theory & mathematics
Maximum difference
Discrete Mathematics and Combinatorics
Mathematics
Subjects
Details
- ISSN :
- 14355914 and 09110119
- Volume :
- 37
- Database :
- OpenAIRE
- Journal :
- Graphs and Combinatorics
- Accession number :
- edsair.doi...........5182a3ba35b8fc6b425152b7fbde5c02