星のような木

次数が2を超える頂点を1つだけ持つ木グラフ

星のような木

グラフ理論と呼ばれる数学の分野において、木が2以上の次数の頂点を1つだけ持つ場合、その木は星型であると言われます。この高次数の頂点は根（または中心頂点）と呼ばれ、星型木はこの中心頂点に少なくとも3つの線型グラフを接続することで得られます。このようなグラフはスパイダーグラフとも呼ばれます。

意味

より正式には、と を正の整数とする。スター型木とは、中心頂点の次数が で、 が頂点上のパスグラフを表し、におけるのすべての近傍は次数が1または2である木である。 における頂点の総数はである。最も単純なスター型木は、枝の長さが1であるスターグラフである。^[1] ${\displaystyle k\geq 3}$ ${\displaystyle n_{1},\ldots ,n_{k}\geq 1}$ ${\displaystyle S(n_{1},\ldots ,n_{k})}$ ${\displaystyle T}$ ${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle T\setminus v\cong P_{n_{1}}\cup \cdots \cup P_{n_{k}}}$ ${\displaystyle P_{t}}$ ${\displaystyle t}$ ${\displaystyle v}$ ${\displaystyle T}$ ${\displaystyle S(n_{1},\ldots ,n_{k})}$ ${\displaystyle n_{1}+\cdots +n_{k}+1}$ ${\displaystyle S_{k}=S(1,\ldots ,1)}$ ${\displaystyle k}$

プロパティ

スペクトル特性

二つの有限星状木は等スペクトルである、すなわちそれらのグラフラプラシアンが同じスペクトルを持つのは、それらが同型である場合に限ります。^[2]グラフラプラシアンには常に4以上の固有値が1つだけあります。^[3]

スペクトル半径の境界

星状木のスペクトル半径（隣接行列の最大固有値）は、その最大次数 で制限される。および の星状木の場合、スペクトル半径は次式を満たす: ^[1] ${\displaystyle \Delta }$ ${\displaystyle S(n_{1},\ldots ,n_{k})}$ ${\displaystyle k\geq 4}$ ${\displaystyle n_{1},\ldots ,n_{k}\geq 2}$ ${\displaystyle \lambda _{1}}$

${\displaystyle {\frac {k-1}{\sqrt {k-2}}}<\lambda _{1}(S(n_{1},\ldots ,n_{k}))<{\frac {k}{\sqrt {k-1}}}}$

あるいは、最大次数に関しても同様である。 ${\displaystyle \Delta =k}$

${\displaystyle {\frac {\Delta -1}{\sqrt {\Delta -2}}}<\lambda _{1}<{\frac {\Delta }{\sqrt {\Delta -1}}}}$

これらの境界は、このような星型ツリーのスペクトル半径が、最大次数が大きくなるにつれて漸近的になることを示しています。 ${\displaystyle {\sqrt {\Delta }}}$

具体的なケース：^[1]

• すべての枝の長さが1の場合、 ${\displaystyle k=3}$ ${\displaystyle \lambda _{1}={\sqrt {3}}}$
• すべての枝の長さが2の場合、 ${\displaystyle k=3}$ ${\displaystyle \lambda _{1}=2}$
• 全ての枝の長さが1（つまり木が星型）の場合、 ${\displaystyle k\geq 4}$ ${\displaystyle S_{k+1}}$ ${\displaystyle \lambda _{1}={\sqrt {k}}}$

区間(-2, 2)の固有値

星状木の固有値は区間 に関して特徴付けられる。3つの枝を持つ星状木が、そのすべての固有値を開区間 に持つ場合、かつその場合のみ、それは次のいずれかと同型である。 ${\displaystyle (-2,2)}$ ${\displaystyle S(n_{1},n_{2},n_{3})}$ ${\displaystyle (-2,2)}$

• ${\displaystyle S(1,1,m)}$任意の正の整数 ${\displaystyle m}$
• ${\displaystyle S(1,2,2)}$、、 または ${\displaystyle S(1,2,3)}$ ${\displaystyle S(1,2,4)}$

4つ以上の枝を持つ星型木の場合、少なくとも1つの固有値は区間外にあります。^[1] ${\displaystyle (k\geq 4)}$ ${\displaystyle (-2,2)}$

位相指標

頂点次数に基づく位相指数は、 と定義される分子記述子である。ここで、は次数 の頂点と次数 の頂点間の辺の数であり、 の値が特定の指数を決定する。例としては、ランディッチ指数、第一ザグレブ指数、調和指数 、原子結合連結性指数 などが挙げられる。^[4] ${\displaystyle TI(G)=\sum _{1\leq i\leq j\leq n-1}m_{ij}(G)\varphi _{ij}}$ ${\displaystyle m_{ij}(G)}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle \varphi _{ij}}$

頂点がで中心次数が の星型木の場合、そのようなインデックスは を満たす。ここで は長さ1、 、の枝の数である。これは、インデックス値が主に単位長さの枝の数に依存することを示している。^[4] ${\displaystyle X}$ ${\displaystyle n}$ ${\displaystyle k}$ ${\displaystyle TI(X)=k_{1}P_{k}+kQ_{k}+(n-1)\varphi _{22}}$ ${\displaystyle k_{1}}$ ${\displaystyle P_{k}=\varphi _{1k}+\varphi _{22}-\varphi _{12}-\varphi _{2k}}$ ${\displaystyle Q_{k}=\varphi _{12}+\varphi _{2k}-2\varphi _{22}}$

頂点上の星型木の中で、極値を得る典型的には、枝付きスターグラフと木である。すべての（ランディッチ指数、調和指数、和連結指数、幾何演算指数、拡張ザグレブ指数を含む）に対して となる指数については、スターグラフは最小値と最大値を達成する。逆のことが成り立つ（第一ザグレブ指数、アルバートソン指数、原子結合連結指数を含む）。^[4] ${\displaystyle n}$ ${\displaystyle S(1,1,\ldots ,1)}$ ${\displaystyle n-1}$ ${\displaystyle S(2,2,n-5)}$ ${\displaystyle P_{k}\leq 0}$ ${\displaystyle k\geq 3}$ ${\displaystyle S(2,2,n-5)}$ ${\displaystyle P_{k}\geq 0}$

参考文献

1. オボウディ、モハマド・レザー (2018 年 8 月)。 「星状樹木の固有値とスペクトル半径について」。数学の方程式。92 (4): 683–694。土井:10.1007/s00010-017-0533-4。ISSN  0001-9054。
2. M. Lepovic, I. Gutman (2001). 星のような木は共スペクトルではない。
3. 中務裕二; 斉藤直樹; ウォーエイ・アーネスト (2013年4月). 「グラフラプラシアン固有値4の謎」.線形代数とその応用. 438 (8): 3231–46 . arXiv : 1112.4526 . doi :10.1016/j.laa.2012.12.012.
4. ベタンクール, クララ; クルーズ, ロベルト; ラダ, フアン (2015). 「星状木上の頂点次数ベースの位相インデックス」.離散応用数学. 185 : 18–25 . doi :10.1016/j.dam.2014.12.021. ISSN  0166-218X.

外部リンク

• ワイスタイン、エリック・W.「スパイダーグラフ」。MathWorld。
• （ OEISの配列A004250）

「https://en.wikipedia.org/w/index.php?title=Starlike_tree&oldid=1322981587」から取得