Multiplicity of Stars in Complete Graphs and Complete $r$-partite Graphs

Abstract

Let $K_r$ be the complete graph on $r$ vertices in which there exists an edge between every pair of vertices, $K_{m,n}$ be the complete bipartite graph with $m$ vertices in one partition and $n$ vertices in the other partition, where each vertex in one partition is adjacent to each vertex in the other partition, and $K(n,r)$ be the complete $r$-partite graph $K_{n,n,\dots ,n}$ where each partition has $n$ vertices. In this paper, we determine the minimum number of monochromatic stars $K_{1,p}$, $\mathrm{\forall }p\ge 2$, in any $t$-coloring ($t\ge 2$) of edges of $K_r$, $K_{m,n}$, and $K(n,r)$. Also, we prove that these lower bounds are sharp for all values of $m,n,p,r$, and $t$ by giving explicit constructions.