THE MINIMUM MULTIPLICITY OF STAR GRAPHS
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
In 1972, the Ramsey number r(Sα, Sβ) with respect to star graphs was given by Harary, where St denotes the star graph of order t + 1. While this number says just the existence of Sα, or Sβ, the compliment of Sβ, in every graph G of order r(Sα, Sβ), it does not exactly say anything about the number of Sα, and Sβ in the graph. In this paper, we first enumerate the total number of star graphs of order t and the complement graphs of star graphs of order t along with the degree sequence of G, denoted by σt(G). Next, we determine the minimum number σt(gn) among σt(G)'s for G ∈ gn, where gn is the set of all graphs of order n. Finally, as a corollary, we construct a ‘minimal graph’ of order r(St, St) in which there are σt(gn) star graphs St's and the compliments of star graphs St's.
Abstract
In 1972, the Ramsey number r(Sα, Sβ) with respect to star graphs was given by Harary, where St denotes the star graph of order t + 1. While this number says just the existence of Sα, or Sβ, the compliment of Sβ, in every graph G of order r(Sα, Sβ), it does not exactly say anything about the number of Sα, and Sβ in the graph. In this paper, we first enumerate the total number of star graphs of order t and the complement graphs of star graphs of order t along with the degree sequence of G, denoted by σt(G). Next, we determine the minimum number σt(gn) among σt(G)'s for G ∈ gn, where gn is the set of all graphs of order n. Finally, as a corollary, we construct a ‘minimal graph’ of order r(St, St) in which there are σt(gn) star graphs St's and the compliments of star graphs St's.
참고문헌 (3)
- Adolph W. Goodman, "On sets of acquaintances and strangers at any party", American Mathematical Monthly, 66(9), pp.778~783 (1959)
- F. Harary, "Graph Theory and Appli-cations", pp.125~138 (1972), Springer Berlin Heidelberg
- Gross, Yellen, "Handbook of graph theory", pp.23~24 (2014), CRC Press