分数支配集合

各頂点とその近傍（閉近傍）の重みの合計は少なくとも1です。したがって、重みの割り当ては分数支配集合です。グラフのすべての重みの合計をすべての分数支配集合にわたって考えることができます。これらの最小値がグラフの分数支配数です。示されているグラフには、合計が である最適な集合 が示されています。${\displaystyle 7/3}$

グラフ理論において、分数支配集合とは支配集合の概念を一般化したもので、頂点に二項帰属ではなく0から1の間の分数重みを割り当てることを可能にします。この緩和により、支配問題は線形計画問題に変換され、より正確な境界が得られ、多項式時間計算が可能になります。

意味

グラフを仮定する。分数支配関数とは、任意の頂点に対して閉近傍の和が少なくとも1となるような関数である。 ^{[1] [2]}${\displaystyle G=(V,E)}$ ${\displaystyle f:V\to [0,1]}$ ${\displaystyle v\in V}$ ${\displaystyle f}$ ${\displaystyle N[v]}$

${\displaystyle \sum _{u\in N[v]}f(u)\geq 1}$

分数支配数は 、分数支配関数の最小の合計重みです。 ${\displaystyle \gamma _{f}(G)}$

${\displaystyle \gamma _{f}(G)=\min \left\{\sum _{v\in V}f(v)\right\}}$

プロパティ

任意のグラフに対して、分数支配数は次式を満たす: ^[1]${\displaystyle G}$

${\displaystyle \gamma _{f}(G)\leq \gamma (G)\leq \Gamma (G)\leq \Gamma _{f}(G)}$

ここで、 は支配数、は上限支配数、は上限分数支配数です。 ${\displaystyle \gamma (G)}$ ${\displaystyle \Gamma (G)}$ ${\displaystyle \Gamma _{f}(G)}$

分数支配数は、強い双対性を利用することで線形計画の解として計算することができる。^[2]

頂点を持つ任意のグラフについて、最小次数、最大次数は次の通りである: ^[2]${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \delta }$ ${\displaystyle \Delta }$

${\displaystyle {\frac {n}{\Delta +1}}\leq \gamma _{f}(G)\leq {\frac {n}{\delta +1}}}$

任意のグラフにおいて、分数辺支配数は線グラフの支配数に等しい：^[3]${\displaystyle G}$

${\displaystyle \gamma '_{f}(G)=\gamma (L(G))}$

特定のグラフファミリーの式

頂点が k 個、頂点が 個のk個正則グラフの場合: ^{[1] [4]}${\displaystyle n}$ ${\displaystyle k\geq 1}$

${\displaystyle \gamma _{f}(G)={\frac {n}{k+1}}}$

完全二部グラフ の場合：^[2]${\displaystyle K_{r,s}}$

${\displaystyle \gamma _{f}(K_{r,s})={\frac {r(s-1)+s(r-1)}{rs-1}}}$

サイクルグラフ の場合：^[3]${\displaystyle C_{n}}$

${\displaystyle \gamma _{f}(C_{n})={\frac {n}{3}}}$

パスグラフ の場合：^[3]${\displaystyle P_{n}}$

${\displaystyle \gamma _{f}(P_{n})=\left\lceil {\frac {n}{3}}\right\rceil }$

クラウングラフ の場合：^[3]${\displaystyle H_{n,n}}$

${\displaystyle \gamma _{f}(H_{n,n})=2}$

頂点付きホイールグラフ の場合: ^[3]${\displaystyle W_{n}}$ ${\displaystyle n>3}$

${\displaystyle \gamma _{f}(W_{n})=1}$

いくつかのグラフクラスには次のものがある: ^[2]${\displaystyle \gamma _{f}(G)=\gamma (G)}$

• 木々
• ブロックグラフ（すべてのブロックが完全なグラフ）
• 強い弦グラフ

グラフの強積 について：^[2]${\displaystyle G\boxtimes H}$

${\displaystyle \gamma _{f}(G\boxtimes H)=\gamma _{f}(G)\cdot \gamma _{f}(H)}$

グラフの直積 （ヴィジングの予想、分数バージョン）の場合： ^[2]${\displaystyle G\square H}$

${\displaystyle \gamma _{f}(G\square H)\geq \gamma _{f}(G)\cdot \gamma _{f}(H)}$

計算の複雑さ

分数支配数は線形計画法として定式化できるため、NP困難である標準支配数とは異なり、多項式時間で計算できます。^[2]

変種

分数距離k支配関数は、すべての頂点 に対して、その距離近傍（から最大で までの距離にある頂点）の和が少なくとも1であることを条件として、この概念を一般化します。対応する分数距離k支配数はと表されます。^[4]${\displaystyle v}$ ${\displaystyle k}$ ${\displaystyle N_{k}[v]}$ ${\displaystyle k}$ ${\displaystyle v}$ ${\displaystyle \gamma _{kf}(G)}$

-正則グラフと特定の値については、厳密な公式が存在する。例えば、閉路については次の式が成り立つ：^[4]${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle C_{n}}$

${\displaystyle \gamma _{kf}(C_{n})={\frac {n}{2k+1}}}$

効率的な分数支配関数は次式を満たす。

${\displaystyle \sum _{u\in N[v]}f(u)=1}$

すべての頂点に対して。すべてのグラフが効率的な分数支配関数を許容するわけではない。^[2]${\displaystyle v}$

分数全支配関数とは、任意の頂点 に対して、その開近傍（自身を除く）の和が少なくとも1となる関数である。分数全支配数は と表記される。^[2]${\displaystyle v}$ ${\displaystyle N(v)}$ ${\displaystyle v}$ ${\displaystyle \gamma _{ft}(G)}$

上側分数支配数は 、すべての最小分数支配関数の中で最大の重みです。^[2]${\displaystyle \Gamma _{f}(G)}$

参照

• 支配的なセット
• 線形計画法
• 分数グラフの色分け

参考文献

1. Haynes, Teresa W.; Hedetniemi, Stephen T.; Slater, Peter J. (1998).グラフにおける支配の基礎. Marcel Dekker. pp.  261– 262. ISBN 9780429157769。
2. ウェイン・ゴダード、マイケル・A・ヘニング (2020). 「分数支配パラメータ」. テレサ・W・ヘインズ、スティーブン・T・ヘデトニエミ、マイケル・A・ヘニング (編).グラフにおける支配の話題. シュプリンガー. pp.  349– 363. doi :10.1007/978-3-030-51117-3_10. ISBN 978-3-030-51117-3。
3. シャンティ、P.;アミュサ、S.アンバザガン、N.ブラガシースワラ プラブ、S. (2023)。 「グラフにおけるフラクショナルドミネーションへの影響」。インテリジェントおよびファジー システムのジャーナル。44 (5): 7855–7864。土井:10.3233/JIFS-222999。
4. アルムガム、S.;マシュー、ヴァルギーズ。 Karuppasamy、K. (2012)。 「グラフにおける分数距離の支配」。数学グラフ理論に関するディスカッション。32 (3): 449–459 .土井: 10.7151/dmgt.1609。