Properties of possible counterexamples to the Seymour's Second Neighborhood Conjecture
The project is devoted to the study of the Seymour’s Second Neighborhood conjecture by determining the properties of possible counterexamples to it. This problem has remained unsolved for more than 30 years, although there is some progress in its solution. The vector of the research is aimed at the analysis of possible counterexamples to the conjecture with the subsequent finding of some of their characteristic values. In addition, attention is focused on the generalized Seymour’s conjecture for vertex-weighted graphs. Combinatorial research methods and graph theory methods were used in the project. The author determines the values of densities and diameters of possible counterexamples, considers separately directed graphs of diameter 3. The conditions under which specific graphs cannot be counterexamples to the Seymour’s conjecture with the minimum number or vertices are defined. The relationship between the Seymour’s conjecture and vertex-weighted Seymour’s conjecture is explained. It is proved that if there exists at least one counterexample, then there exist counterexamples with an arbitrary diameter not less than 3. Under the same condition, the existence of counterexamples with a density both close to 0 and close to 1 is also proved. The equivalence of the above two conjectures is substantiated in detail. It can be concluded that if the Seymour’s Second Neighborhood Conjecture is true for a directed graph of diameter 3, then it is true for any digraph, so that problem will be solved. Moreover, if the conjecture is true, then vertex-weighted version of this conjecture is true too. That is why a digraph of diameter 3 needs further research.
3進位Kaprekar變換之結構
b進位的n位數字x，數字x各位數字由大到小排列為p，由小到大排列為q，定義Kaprekar變換T(b,n)(x)=p-q，例如T(10,3)(x)= 954-459。當T(b,n)(x)= x，稱x為Kaprekar常數。 Tk(b,n)( x)=T(b,n)( Tk-1(b,n)( x))= x, k >1時，稱x為k階Kaprekar循環數。本文解答了以下問題： 1. b進位的數字不包含數字b-1的Kaprekar常數的形式。 2. 3,4,5,6進位的Kaprekar常數的一般形式。 3. 對於2,3進位的情形，我們引入三元非負整數的形式來討論Kaprekar變換，轉換成Kaprekar數對(p,q)，再進一步，由來探討比值p/q，將Kaprekar變換轉成Kaprekar函數g(x)，解決 Kaprekar 循環數的所有形式及解。 最後我們得到Tl(b,n)( x)必是Kaprekar循環數。
Properties of possible counterexamples to the Seymour's Second Neighborhood Conjecture
The project is devoted to the study of the Seymour’s Second Neighborhood conjecture by determining the properties of possible counterexamples to it. This problem has remained unsolved for more than 30 years, although there is some progress in its solution. The vector of the research is aimed at the analysis of possible counterexamples to the conjecture with the subsequent finding of some of their characteristic values. In addition, attention is focused on the generalized Seymour’s conjecture for vertex-weighted graphs. Combinatorial research methods and graph theory methods were used in the project. The author determines the values of densities and diameters of possible counterexamples, considers separately directed graphs of diameter 3. The conditions under which specific graphs cannot be counterexamples to the Seymour’s conjecture with the minimum number or vertices are defined. The relationship between the Seymour’s conjecture and vertex-weighted Seymour’s conjecture is explained. It is proved that if there exists at least one counterexample, then there exist counterexamples with an arbitrary diameter not less than 3. Under the same condition, the existence of counterexamples with a density both close to 0 and close to 1 is also proved. The equivalence of the above two conjectures is substantiated in detail. It can be concluded that if the Seymour’s Second Neighborhood Conjecture is true for a directed graph of diameter 3, then it is true for any digraph, so that problem will be solved. Moreover, if the conjecture is true, then vertex-weighted version of this conjecture is true too. That is why a digraph of diameter 3 needs further research.
Locus of the Points on Circumference of the n-th Circle that Formed by Moving the Center of any Radius Circles on the Outermost Circumference of Preceding set of Circles
This project aimed to study the motion which occurred from the end point on the circumference of the outermost circle by moving the center on the circumference of a preceding circle and the center of an innermost circle at origin. According to the study, when angular velocity was changed, it caused the different of loci. Based on the above information, finding the locus of the point on circumference of n-th circle that formed by moving the center of any radius circles on circumference of preceding set of circles was studied to get general equation. A set of circle and locus were created with GSP program. First, set the same radius circles on the X-axis with the first circle at origin, then found the relationship that occurred from the characteristics of locus. The result showed that if the ratios of angular velocity are 1:1:1, 2:2:2, 3:3:3, ..., …, n:n:n or 1:2:3, 2:4:6, 3:6:9, …,nw1:nw2:nw3, the characteristics of locus will be the same, while the others will be different. Finally, the equation of locus was found as follow: (x,y) = { ..........see in abstract...........} when .........see in abstract........... Where ri is the radius of i-th circle, zeta i is an angle between the radius of i-th circle and X-axis, wi is the angular velocity, t is elapsed time and alpha i is a starting angle between the radius of i-th circle and X-axis.