友情グラフ

友情グラフ
友情グラフF 8。
頂点	2n +1です
エッジ	3位
半径	1
直径	2
胴回り	3
彩度数	3
色指数	2位
プロパティ	単位距離 平面 オイラー 重要な要素 局所的に線形
表記	ファn
グラフとパラメータの表

数学のグラフ理論の分野において、友情グラフ（オランダ風車グラフ、 nファングラフともいう）Fn_は、2n +1個の頂点と3n個の辺を持つ平面の無向グラフである。^[1]

友情グラフFn_は、サイクルグラフC3のn個のコピーを共通の頂点で結合することによって構築することができ、その頂点_はグラフの普遍的な頂点となる。 ^[2]

構築により、友情グラフF _{n は}風車グラフWd(3, n )と同型です。これは、周囲長3、直径 2、半径 1の単位距離です。グラフF _{2 は}蝶のグラフと同型です。友情グラフは、三角形のサボテングラフによって一般化されます。

ポール・エルデシュ、アルフレッド・レーニ、ヴェラ・T・ソス (1966) ^[3]による友情定理は、2 つの頂点ごとにちょうど 1 つの隣接頂点が共通するという性質を持つ有限グラフがまさに友情グラフであると述べています。非公式には、あるグループの人々のペアごとにちょうど 1 人の友人が共通するという性質がある場合、他のすべての人々の友人である人が 1 人いるはずです。ただし、無限グラフの場合、この性質を持つ同じ基数を持つさまざまなグラフが多数存在する可能性があります。^[4]

友情定理の組み合わせ論的証明は、MertziosとUngerによって与えられました。^[5]別の証明はCraig Hunekeによって与えられました。^[6] Metamathでの形式化された証明は、2018年10月にAlexander van der VekensによってMetamathメーリングリストで報告されました。^[7]

友情グラフは彩色数3、彩色指数 2 nを持ち、その彩色多項式はサイクルグラフC ₃の彩色多項式から演繹でき、次の式に等しい。

${\displaystyle (x-2)^{n}(x-1)^{n}x}$。

友情グラフF _{n は}、 nが奇数のときのみ辺優美である。n ≡ 0 (mod 4)またはn ≡ 1 (mod 4)のときのみ辺優美である。^[8] [ ^9]

すべての友情グラフは因子的に重要です。

極値グラフ理論によれば、十分な数の辺（頂点の数に比べて）を持つすべてのグラフは、必ず部分グラフとして -ファンを含む。より具体的には、辺の数が ${\displaystyle k}$${\displaystyle n}$

${\displaystyle \left\lfloor {\frac {n^{2}}{4}}\right\rfloor +f(k),}$

ここで、が奇数の場合は、 が 偶数の場合はです。これらの境界は、三角形のないグラフの辺の数に関するトゥランの定理を一般化したものであり、この問題に対する最良の境界であり、より小さな辺の数に対しては -ファンを含まないグラフが存在する。^[10]${\displaystyle f(k)}$${\displaystyle k^{2}-k}$${\displaystyle k}$${\displaystyle f(k)}$${\displaystyle k^{2}-3k/2}$${\displaystyle k}$${\displaystyle k}$

ちょうど 1 つの隣接頂点を共有する任意の 2 つの頂点は、長さ 2 の 1 つのパスによって接続された任意の 2 つの頂点と同等です。これは、任意の 2 つの頂点が長さ の一意のパスによって接続される -グラフに一般化されています。このようなグラフは知られておらず、その非存在を主張するのがKotzig の予想です。 ${\displaystyle P_{k}}$${\displaystyle k}$${\displaystyle k\geq 3}$