折れ線グラフ

数学の分野であるグラフ理論では、無向グラフ $G$ の線グラフは、 $G$ の辺間の隣接関係を表す別のグラフ $L($ $G$ $)$ です。 $L($ $G$ $) は$ 、次のように構築されます。 $Gの各辺に対して、$ $L($ $G$ $)$ に頂点を作成します。 $G$ で共通の頂点を持つ 2 つの辺ごとに、 $L($ $G$ $)$ の対応する頂点間に辺を作成します。

線グラフという名前は、Harary & Norman (1960) の論文に由来していますが、Whitney (1932) と Krausz (1943) の両者がこの論文以前にこの構築法を使用していました。^[1]線グラフに使用される他の用語には、被覆グラフ、導関数、辺頂点双対、共役、代表グラフ、θ-オブラゾン^{[1] 、}およびエッジグラフ、交換グラフ、随伴グラフ、導出グラフなどがあります。^[2]

ハスラー・ホイットニー（1932）は、例外的なケースを1つ除いて、連結グラフ $G$ の構造をその線グラフから完全に復元できることを証明した。^[3]線グラフの他の多くの特性は、基礎となるグラフの特性を頂点から辺に変換することによって得られ、ホイットニーの定理により、同じ変換を逆方向に行うこともできる。線グラフはクローフリーであり、二部グラフの線グラフは完全である。線グラフは9つの禁制部分グラフによって特徴付けられ、線形時間で認識できる。

線グラフの概念のさまざまな拡張が研究されており、線グラフの線グラフ、マルチグラフの線グラフ、ハイパーグラフの線グラフ、重み付きグラフの線グラフなどがあります。

正式な定義

グラフ $G$ が与えられたとき、その線グラフ $L (G)$ は次のようなグラフである。

$L$ $($ $G$ $)$ の各頂点は $G$ の辺を表す。
$L (G)$ の2つの頂点が隣接しているのは、それらの対応する辺が $G$ 内で共通の端点を共有する（「接続している」）場合のみです。

つまり、これは $G$ の辺の交差グラフであり、各辺はその2つの端点の集合によって表される。^[2]

例

次の図は、グラフ (左、青い頂点) とその折れ線グラフ (右、緑の頂点) を示しています。折れ線グラフの各頂点には、元のグラフの対応する辺の端点のペアがラベル付けされています。たとえば、右側の 1,3 とラベル付けされた緑の頂点は、左側の青い頂点 1 と 3 の間の辺に対応しています。緑の頂点 1,3 は、他の 3 つの緑の頂点 1,4 と 1,2 (青いグラフの端点 1 を共有する辺に対応)、および 4,3 (青いグラフの端点 3 を共有する辺に対応) に隣接しています。

グラフG
Gの辺から構成されるL( G )の頂点
L( G )に追加されたエッジ
折れ線グラフL( G )

プロパティ

基礎となるグラフの翻訳されたプロパティ

グラフ $G$ の辺同士の隣接性のみに依存する性質は、頂点同士の隣接性に依存する $L (G)$ の同等の性質に変換できる。例えば、 $G$ のマッチングは、2 つの辺が隣接していない辺の集合であり、 $L$ $($ $G$ $)$ の2 つの頂点が隣接していない頂点の集合、つまり独立集合に対応する。^[4]

したがって、

連結グラフの線グラフは連結である。Gが連結であれば $、$ その2辺を結ぶパスが含まれ、これは $L$ $($ $G$ $)$ の任意の2頂点を含む $L$ $($ $G$ $)$ のパスに変換される。しかし、いくつかの孤立した頂点を持ち、したがって連結されていないグラフ $G$ でも、連結線グラフを持つことがある。^[5]
線グラフが連結点を持つのは、基礎となるグラフに、どちらの端点も次数1を持たない橋がある場合に限られます。 ^[2]
$n 個の$ 頂点と $m$ 個の辺を持つグラフ $G$ の場合、線グラフ $L$ $($ $G$ $)の頂点の数は$ $m$ であり、 $L$ $($ $G$ $)$ の辺の数は $G$ の頂点の次数の二乗の合計の半分から $m を$ 引いた数である。^[6]
$L$ $($ $G$ $)$ の独立集合は $G$ のマッチングに対応する。特に、 $L$ $($ $G$ $)$ の最大独立集合は $G$ の最大マッチングに対応する。最大マッチングは多項式時間で見つけられるので、より一般的なグラフ族の最大独立集合問題の困難さにもかかわらず、線グラフの最大独立集合も同様に見つけられる可能性がある。^[4]同様に、 $L$ $($ $G$ $)$ のレインボー独立集合は $G$ のレインボーマッチングに対応する。
グラフ $Gの$ 辺彩色数はその線グラフ $L$ $($ $G$ $)$ の頂点彩色数に等しい。^[7]
辺推移グラフの線グラフは頂点推移的である。この性質は、（ピーターセングラフのように）頂点推移的だがケイリーグラフではないグラフの族を生成するために使用できる。すなわち、 $G$ が少なくとも5つの頂点を持ち、二部グラフではなく、頂点次数が奇数である辺推移グラフである場合、 $L (G)は$ 頂点推移的な非ケイリーグラフである。^[8]
グラフ $Gに$ オイラー閉路がある場合、つまり $G$ が連結で各頂点に偶数個の辺がある場合、 $Gの線グラフは$ ハミルトンです。しかし、線グラフのハミルトン閉路のすべてがこのようにオイラー閉路から派生するわけではありません。たとえば、ハミルトングラフ $Gの線グラフは、$ $G$ がオイラーであるかどうかに関係なく、それ自体がハミルトンです。^[9]
2 つの単純なグラフが同型である場合、それらの線グラフも同型です。ホイットニーのグラフ同型定理は、連結されたグラフの 1 組を除くすべてのグラフに対して、これの逆を提供します。
複雑ネットワーク理論の文脈では、ランダムネットワークの線グラフは、スモールワールド特性（すべての頂点ペアの間に短いパスが存在する）や次数分布の形状など、ネットワークの多くの特性を保持します。^[10] EvansとLambiotte（2009）は、複雑ネットワーク内の頂点クラスターを見つけるための任意の方法を線グラフに適用して、代わりにそのエッジをクラスター化するために使用できることを指摘しています。

ホイットニー同型定理

連結された2つのグラフの線グラフが同型であれば、その基となるグラフも同型である。ただし、三角形グラフ $K 3$ とクローグラフ $K 1,3$ は線グラフは同型だが、それ自体は同型ではない。^[3]

$K 3$ や $K 1,3 の$ 他にも、グラフ自体よりも線グラフの対称性が高いという特性を持つ例外的な小グラフがいくつかあります。たとえば、ダイヤモンドグラフ $K 1,1,2$ (2 つの三角形が 1 つの辺を共有) には 4 つのグラフ自己同型がありますが、線グラフ $K 1,2,2$ には 8 つの自己同型があります。ダイヤモンドグラフの図では、グラフを 90 度回転することはグラフの対称性ではなく、線グラフの対称性です。ただし、このような例外的なケースはすべて、最大で 4 つの頂点を持ちます。ホイットニー同型定理の強化版では、4 つ以上の頂点を持つ連結グラフの場合、グラフの同型と線グラフの同型の間に 1 対 1 の対応関係があることが述べられています。^[11]

ホイットニー同型定理の類似物は多重グラフの線グラフに対しても証明されているが、この場合はより複雑である。^[12]

強く規則的で完全な折れ線グラフ

完全グラフ $K n$ の線グラフは、三角グラフ、ジョンソングラフ $J (n, 2)$ 、またはクネザーグラフ $KG$ $n$ $,2$ の補グラフとしても知られています。三角グラフは、 $n$ $= 8$ $を$ 除いて、スペクトルによって特徴付けられます。^[13]これらはまた、パラメータ $srg($ $n$ $($ $n$ $- 1)/2, 2($ $n$ $- 2),$ $n$ $- 2, 4)$ $を$ 持つ強正則グラフとして特徴付けられることもあります (これも K 8を除きます) 。^[14] $L$ $($ $K$ $8$ $)$ と同じパラメータとスペクトルを持つ 3 つの強正則グラフは、 $L$ $($ $K$ $8$ $)$ からグラフを切り替えることで得られるチャングラフです。

二部グラフの線グラフは完全である（ケーニッヒの定理を参照）が、クローグラフの例が示すように二部である必要はない。二部グラフの線グラフは、完全グラフの重要な構成要素の1つであり、強い完全グラフ定理の証明に使用されている。^[15]これらのグラフの特殊なケースは、ルークのグラフ、つまり完全二部グラフの線グラフである。完全グラフの線グラフと同様に、これらは、頂点の数、辺の数、隣接点と非隣接点の共有近傍の数という1つの例外を除いて特徴付けることができる。唯一の例外ケースは $L （ K 4,4 ）であり、これは$ シュリカンデグラフとパラメータを共有する。二分割の両側の頂点の数が同じである場合、これらのグラフは再び強正則である。^[16]

より一般的には、グラフ $G は、$ $L$ $($ $G$ $)が$ 完全グラフである場合に、線完全グラフであると言われる。線完全グラフとは、3 より大きい奇数長の単純閉路を含まないグラフである。 ^[17]同様に、グラフが線完全であるためには、その2 連結成分のそれぞれが2 部グラフであるか、 $K$ $4$ (四面体) または $K$ $1,1,$ $n$ (共通の辺を共有する 1 つ以上の三角形のブック) のいずれかの形をとる必要がある。^[18]すべての線完全グラフは、それ自体が完全である。^[19]

その他の関連グラフファミリー

すべての線グラフはクローフリーグラフであり、3葉の木の形で誘導された部分グラフを持たないグラフです。 ^[20]より一般的なクローフリーグラフと同様に、偶数の辺を持つすべての接続された線グラフ $L (G)は$ 完全なマッチングを持ちます。^[21]同様に、これは、基になるグラフ $Gに$ 偶数の辺がある場合、その辺を2辺のパスに分割できることを意味します。

木の線グラフはまさにクローフリーブロックグラフです。^{[22]これらのグラフは、}極限グラフ理論における問題を解決するために使用されてきました。その問題は、与えられた数の辺と頂点を持つグラフを構築し、その部分グラフとして誘導される最大の木が可能な限り小さくなるようにすることです。^[23]

線グラフの隣接行列 $A$ のすべての固有値は少なくとも-2である。これは、 $A$ がと書けるからである。ここで、 $J$ はプレ線グラフの符号なし接続行列であり、 $Iは$ 単位行列である。特に、 $A$ $+ 2$ $Iは$ ベクトル系のグラミアン行列である。この特性を持つすべてのグラフは一般化線グラフと呼ばれている。^[24] $A=J^{\mathsf {T}}J-2I$

特徴づけと認識

クリーク分割

任意のグラフ $Gと$ $G$ 内の任意の頂点 $vについて、$ $v$ に接続する辺の集合は、線グラフ $L$ $($ $G$ $)内の$ クリークに対応します。このようにして形成されたクリークは、 $L$ $($ $G$ $)$ の辺を分割します。 $L$ $($ $G$ $)$ の各頂点は、それらの 2 つ ( $G$ 内の対応する辺の 2 つの端点に対応する 2 つのクリーク) に属します。

このようなクリークへの分割の存在は、線グラフを特徴付けるために使用できます。グラフ $L$ が他のグラフまたはマルチグラフの線グラフである場合、 L の各頂点がちょうど $2$ つのクリークに属するように、 L の辺を分割するクリークのコレクション (一部のクリークは単一の頂点である可能性がある) が L 内に見つかる可能性があります。[20] このクリークの集合が、 L のどの2つの頂点 $も$ 同じ $2$ つのクリークに存在しない^という $追加$ 条件を満たす場合、それはグラフの線グラフです (マルチグラフではありません) 。このようなクリークのファミリーが与えられた場合、各クリークに対して $G$ に1つの頂点を作成し、 L の各頂点に対して $G$ に辺を作成し、その端点が $L$ $の$ 頂点を含む2つのクリークになるようにすることで、 $L$ が線グラフである基礎となるグラフ $G$ を復元できます。ホイットニーの同型定理の強いバージョンによれば、基礎となるグラフ $G$ に 4 つ以上の頂点がある場合、このタイプのパーティションは 1 つしか存在できません。

たとえば、この特徴付けは、次のグラフが折れ線グラフではないことを示すために使用できます。

この例では、中央の 4 次頂点から上、左、右に向かうエッジには共通のクリークがありません。したがって、グラフのエッジをクリークに分割する場合、これらの 3 つのエッジのそれぞれに少なくとも 1 つのクリークが必要です。また、これらの 3 つのクリークはすべて中央の頂点で交差するため、各頂点が正確に 2 つのクリークに出現するという要件に違反します。したがって、示されているグラフは折れ線グラフではありません。

禁止されたサブグラフ

線グラフの別の特徴付けは、Beineke (1970) で証明された（Beineke (1968) によって証明なしに以前に報告されていた）。彼は、線グラフではない極小グラフが 9 つ存在し、線グラフではないグラフはいずれも、これら 9 つのグラフのいずれかを誘導サブグラフとして持つことを示した。つまり、グラフが線グラフであるためには、その頂点のサブセットがこれら 9 つのグラフのいずれかを誘導しない必要がある。上記の例では、最上位の 4 つの頂点がクロー（つまり、完全な 2 部グラフ $K 1,3$ ）を誘導し、禁制サブグラフの図の左上に示されている。したがって、Beineke の特徴付けによれば、この例は線グラフではない。最小次数が少なくとも 5 であるグラフの場合、特徴付けには図の左列と右列の 6 つのサブグラフのみが必要である。^[25]

アルゴリズム

Roussopoulos (1973) と Lehot (1974) は、線グラフを認識して元のグラフを再構築するための線形時間アルゴリズムを説明しました。Sysło (1982) は、これらの方法を有向グラフに一般化しました。Degiorgi と Simon (1995) は、頂点の挿入と削除を条件として動的グラフを維持し、各ステップで変更されたエッジの数に比例した時間で入力の線グラフ (存在する場合) としての表現を維持するための効率的なデータ構造を説明しました。

Roussopoulos (1973) と Lehot (1974) のアルゴリズムは、奇数三角形 (奇数個の三角形の頂点に隣接する別の頂点が存在するという特性を持つ折れ線グラフ内の三角形) を含む折れ線グラフの特性に基づいています。ただし、Degiorgi & Simon (1995) のアルゴリズムは、Whitney の同型定理のみを使用します。残りのグラフが折れ線グラフになる原因となる削除を認識する必要があるため複雑ですが、静的認識問題に特化すると、挿入のみを実行する必要があり、アルゴリズムは次の手順を実行します。

頂点を 1 つずつ追加して入力グラフ $Lを構築します。各ステップで、追加する頂点として、以前に追加された頂点の少なくとも 1 つに隣接する頂点を選択します。$ $Lに頂点を追加している間、$ $L$ $=$ $L$ $($ $G$ $)$ となるグラフ $G を維持します。アルゴリズムが適切なグラフ$ $G を$ 見つけられなかった場合、入力は線グラフではないため、アルゴリズムは終了します。
頂点 $v を、$ $頂点$ が 4 つ以下のグラフ $L (G)$ に追加すると、線グラフの表現が一意ではなくなる可能性があります。ただし、この場合、拡張されたグラフは十分に小さいため、線グラフとしての表現は、総当たり検索によって定数時間で見つけることができます。
頂点 $v を別のグラフ$ $G$ の線グラフに等しい大きなグラフ $L$ に追加する場合、 $L$ 内の $v$ の隣接に対応する辺によって形成される $G$ のサブグラフを $S$ とします。 $S に、$ 1 つの頂点または 2 つの隣接しない頂点からなる頂点カバーがあることを確認します。カバー内に 2 つの頂点がある場合は、これら 2 つの頂点を接続する辺 ( $v$ に対応) を追加して $G を$ 拡張します。カバー内に頂点が 1 つしかない場合は、この頂点に隣接する新しい頂点を $G$ に追加します。

各ステップは一定の時間がかかるか、グラフ $S内で一定サイズの頂点カバーを見つけることを伴います。このサイズは$ $v$ の隣接点の数に比例します。したがって、アルゴリズム全体の合計時間は、すべての頂点の隣接点の数の合計に比例し、これは (ハンドシェイク補題により) 入力エッジの数に比例します。

折れ線グラフ演算子の反復

van Rooij & Wilf (1965) はグラフの順序を考察

G,L(G),L(L(G)),L(L(L(G))),\dots .\

$彼らは、 G が$ 有限連結グラフである場合、このシーケンスに対して可能な動作は 4 つだけであることを示しています。

$Gが$ サイクルグラフである場合、 $L (G)$ と、このシーケンス内の後続の各グラフは $G$ 自体に同型です。これらは、 $L$ $($ $G$ $)が$ $G$ に同型である唯一の連結グラフです。^[26]
$G$ が爪 $K 1,3$ の場合、 $L (G)$ およびシーケンス内の後続のグラフはすべて三角形になります。
$Gが$ パスグラフである場合、シーケンス内の後続の各グラフはより短いパスとなり、最終的にシーケンスは空のグラフで終了します。
残りのすべてのケースでは、このシーケンス内のグラフのサイズは最終的に無制限に増加します。

$G$ が接続されていない場合、この分類は $G$ の各コンポーネントに個別に適用されます。

パスではない連結グラフの場合、線グラフ操作の反復回数が十分に多いと、ハミルトングラフが生成されます。^[27]

一般化

中位グラフと凸多面体

平面グラフ $G$ の最大頂点次数が 3 のとき、その線グラフは平面であり、 $Gのすべての平面埋め込みは$ $L (G)$ の埋め込みに拡張できます。ただし、線グラフが非平面である、より高い次数の平面グラフも存在します。これらには、たとえば、5 つ星 $K 1,5$ 、正五角形内に 2 つの交差しない対角線を追加して形成される宝石グラフ、および次数が 4 以上の頂点を持つすべての凸多面体が含まれます。 ^[28]

代替構成である中間グラフは、最大次数が3の平面グラフの線グラフと一致するが、常に平面である。中間グラフは線グラフと同じ頂点を持つが、潜在的に辺の数は少ない。中間グラフの2つの頂点が隣接するのは、対応する2つの辺が平面埋め込みの何らかの面上で連続している場合に限る。平面グラフの双対グラフの中間グラフは、元の平面グラフの中間グラフと同じである。^[29]

正多面体や単純多面体の場合、グラフの中間操作は、多面体の各頂点を、そのすべての辺の中点を通る平面で切断する操作によって幾何学的に表現できます。^[30]この操作は、第2の切断、^[31]退化した切断、^[32]または整流化などさまざまな名前で知られています。^[33]

合計グラフ

グラフ $G$ の全体グラフ $T (G)は、$ $G$ の要素（頂点または辺）を頂点とし、2つの要素が隣接または隣接する場合は常に2つの要素の間に辺を持ちます。全体グラフは、 $Gの各辺を細分化し、細分化したグラフの$ 2乗をとることによっても得られます。^[34]

マルチグラフ

$G$ の線グラフの概念は、 $G$ が多重グラフの場合にも自然に拡張できる。この場合、これらのグラフの特徴付けは単純化できる。クリーク分割による特徴付けでは、2つの頂点が同じクリークに属することを防ぐ必要がなくなり、禁制グラフによる特徴付けでは、禁制グラフが9つではなく7つになる。^[35]

しかし、多重グラフの場合、同じ線グラフを持つ非同型グラフのペアは多数存在します。たとえば、完全二部グラフ $K 1, n は$ 、双極子グラフと同じ線グラフと、同じ辺数を持つシャノン多重グラフを持ちます。それでも、この場合もホイットニーの同型定理に類似したものを導くことができます。^[12]

線分有向グラフ

線グラフを有向グラフに一般化することも可能です。^[36] $G$ が有向グラフである場合、その有向線グラフまたは線有向グラフは、 $G$ の各辺に対して 1 つの頂点を持ちます。 $G$ 内の $uから$ $v$ および $w$ から $x$ への有向辺を表す 2 つの頂点は、 $v$ $=$ $w$ のとき、線有向グラフ内の $uvから$ $wx$ への辺によって接続されます。つまり、 $Gの線有向グラフ内の各辺は、$ $G$ 内の長さ 2 の有向パスを表します。de Bruijn グラフは、完全な有向グラフから始めて、有向線グラフを形成するこのプロセスを繰り返すことによって形成されます。^[37]

加重折れ線グラフ

線グラフ $L (G)$ では、元のグラフ $Gの次数$ $kの各頂点が、線グラフに$ $k$ $($ $k$ $- 1)/2 個の$ エッジを作成します。多くの種類の分析では、これは $G$ の高次ノードが線グラフ $L$ $($ $G$ $)$ で過剰に表現されていることを意味します。たとえば、元のグラフ $G$ の頂点でのランダムウォークを考えてみましょう。これは、あるエッジ $e を$ ある頻度 $f$ で通過します。一方、このエッジ $e は$ 、線グラフ $L$ $($ $G$ $)$ 内の一意の頂点、たとえば $vにマッピングされます。ここで、線グラフの頂点で同じ種類のランダムウォークを実行すると、$ $v$ が訪問される頻度は、 fとはまったく異なる場合があります。Gのエッジ $e が次数$ $O$ $($ $k$ $)$ のノードに接続されていた場合、線グラフ $L$ $($ $G$ $)では$ $O$ $($ $k$ $2$ $)$ より頻繁にトラバース $さ$ れます。言い換えれば、ホイットニーグラフ同型定理は、線グラフが元のグラフ $G$ の位相をほぼ常に忠実にエンコードすることを保証しますが、これら 2 つのグラフ上のダイナミクスが単純な関係を持つことは保証しません。 1 つの解決策は、重み付き線グラフ、つまり重み付きエッジを持つ線グラフを構築することです。これを行うにはいくつかの自然な方法があります。^[38]たとえば、グラフ $Gのエッジ$ $d$ と $e が$ 次数 $k$ の頂点 $v$ に接続されている場合、線グラフ $L$ $($ $G$ $)で 2 つの頂点$ $d$ と $e を$ 接続するエッジに重み $1/($ $k$ $- 1)$ を与えることができます。このように、 $G$ のすべてのエッジ(どちらの端も次数 1 の頂点に接続されていないことを条件) は、 $G$ でエッジが持つ 2 つの端に対応する線グラフ $L$ $($ $G$ $)で強度 2 を持ちます。この重み付き線グラフの定義を、元のグラフ$ $G$ が有向グラフまたは重み付きグラフである場合に拡張するのは簡単です。 ^[39] いずれの場合も、原則として、線グラフ $L (G) が元のグラフ$ $G$ のトポロジーだけでなくダイナミクスも反映するようにします。

ハイパーグラフの線グラフ

ハイパーグラフのエッジは任意の集合の族を形成することがあるため、ハイパーグラフの線グラフはその族の集合の交差グラフと同じになります。

分離グラフ

$G$ の分離グラフD $($ $G$ $)$ $は$ 次のように構築されます: $Gの各辺に対して、$ $D$ $($ $G$ $)$ に頂点を作成します。 $G内の共通の頂点を$ 持たない2つの辺ごとに、 $D$ $($ $G$ $)$ 内の対応する頂点の間に辺を作成します。^[40]言い換えると、 $D$ $($ $G$ $)は$ $L$ $($ $G$ $)$ の補グラフです。 $D$ $($ $G$ $)$ のクリークは $L$ $($ $G$ $)$ の独立集合に対応し、その逆も同様です。

注記

^ ヘミンガー＆ベイネケ（1978）、273ページ。
^ abc Harary (1972)、71ページ。
^ ab Whitney (1932); Krausz (1943); Harary (1972)、定理8.3、p. 72。Hararyは、Jung (1966)によるこの定理の簡略化された証明を与えている。
^ ab Paschos, Vangelis Th. (2010)、組み合わせ最適化と理論計算機科学：インターフェースと展望、John Wiley & Sons、p. 394、ISBN 9780470393673明らかに、グラフのマッチングとその線グラフの独立集合の間には 1 対 1 の対応があります。
^ 線グラフの接続性を考慮する際に孤立した頂点を考慮する必要があることは、Cvetković、Rowlinson、Simić (2004)、32 ページで指摘されています。
^ Harary (1972)、定理 8.1、p. 72.
^ Diestel, Reinhard (2006)、グラフ理論、Graduate Texts in Mathematics、vol. 173、Springer、p. 112、ISBN 9783540261834無料オンライン版の第 5 章 (「カラーリング」)、118 ページにも掲載されています。
^ ラウリ、ヨゼフ、スカペラート、ラファエレ (2003)、「グラフ自己同型と再構築に関するトピック」、ロンドン数学会学生テキスト、第 54 巻、ケンブリッジ: ケンブリッジ大学出版局、p. 44、ISBN 0-521-82151-7、MR 1971819ラウリとスカペラートはこの結果をマーク・ワトキンスに帰した。
^ Harary (1972)、定理 8.8、p. 80.
^ ラメザンプール、カリミプール、マシャギ (2003)。
^ ユング (1966);デジョルジとサイモン (1995)。
^ アブ・ズヴェロヴィッチ（1997）
^ van Dam, Edwin R.; Haemers, Willem H. (2003)、「どのグラフがそのスペクトルによって決定されるか?」、線形代数とその応用、373 : 241–272、doi : 10.1016/S0024-3795(03)00483-X、MR 2022290、S2CID 32070167特に命題8（262ページ）を参照。
^ Harary (1972)、定理8.6、p. 79。Hararyはこの結果を、LC Chang (1959)とAJ Hoffman (1960)による独立した論文によるものとしている。
^ マリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマス(2006)、「強い完全グラフ定理」、数学年報、164 (1): 51–229、arXiv : math/0212070、doi :10.4007/annals.2006.164.51、S2CID 119151552. Roussel, F.、Rusu, I.、Thuillier, H. (2009)、「強い完全グラフ予想: 40 年間の試みとその解決」、Discrete Mathematics、309 (20): 6092–6113、doi : 10.1016/j.disc.2009.05.024、MR 2552645、S2CID 16049392も参照。。
^ Harary (1972)、定理 8.7、p. 79。Harary は、完全二部グラフの線グラフのこの特徴付けを Moon と Hoffman に帰した。両側の頂点の数が等しいケースは、以前に Shrikhande によって証明されていた。
^ トロッター (1977);デ・ウェラ (1978)。
^ マフレー（1992年）。
^ トロッター（1977年）。
^ ab Harary (1972)、定理 8.4、p. 74 では、線グラフの 3 つの同等な特徴付けが示されています。それは、辺をクリークに分割すること、クローフリーで奇数のダイヤモンドフリーである性質、および Beineke の 9 つの禁制グラフです。
^ サムナー、デイビッド・P. (1974)、「1因子グラフ」、アメリカ数学会紀要、42 (1)、アメリカ数学会: 8–12、doi :10.2307/2039666、JSTOR 2039666、MR 0323648。Las Vergnas, M. (1975)、「グラフのマッチングに関するメモ」、Cahiers du Centre d'Études de Recherche Opérationnelle、17 (2–3–4): 257–260、MR 0412042。
^ Harary (1972)、定理8.5、p. 78。Hararyはこの結果をGary Chartrandに帰している。
^ エルデシュ、ポール;サックス、マイケル;ソス、ヴェラ T. (1986)、「グラフの最大誘導木」、Journal of Combinatorial Theory、シリーズ B、41 (1): 61–79、doi : 10.1016/0095-8956(86)90028-6。
^ ツヴェトコビッチ、ローリンソン、シミッチ (2004)。
^ メテルスキー＆ティシュケビッチ（1997）
^ この結果はHarary (1972)の定理8.2でもある。
^ Harary (1972)、定理8.11、p. 81。Hararyはこの結果をGary Chartrandに帰している。
^ セドラチェク (1964);グリーンウェルとヘミンジャー (1972)。
^ アーチディーコン、ダン（1992）、「メディアルグラフと電圧-電流双対性」、離散数学、104（2）：111–141、doi：10.1016/0012-365X（92）90328-D、MR 1172842。
^ McKee, TA (1989)、「地理的双対性のグラフ理論モデル」、Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985)、Ann. New York Acad. Sci.、vol. 555、ニューヨーク: New York Acad. Sci.、pp. 310–315、Bibcode :1989NYASA.555..310M、doi :10.1111/j.1749-6632.1989.tb22465.x、MR 1018637、S2CID 86300941。
^ ピュー、アンソニー（1976）、多面体：視覚的アプローチ、カリフォルニア大学出版局、ISBN 9780520030565。
^ ローブ、アーサー・リー（1991）、空間構造—その調和と対位法（第5版）、ビルクハウザー、ISBN 9783764335885。
^ Weisstein, Eric W.「Rectification」。MathWorld。
^ ハラリー（1972）、82ページ。
^ Ryjáček & Vrána (2011).
^ ハラリー＆ノーマン（1960年）。
^ 張・林（1987年）。
^ エヴァンス＆ランビオット（2009年）。
^ エヴァンス＆ランビオット（2010年）。
^ Meshulam, Roy (2001-01-01). 「クリーク複合体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.

参考文献

Beineke, LW (1968)、「Derived charts of digraphs」、Sachs, H.;ヴォス、H.-J.ウォルター、H.-J. (編)、Beiträge zur Graphentheorie、ライプツィヒ: Teubner、17–33 ページ。
Beineke, LW (1970)、「導出グラフの特徴付け」、Journal of Combinatorial Theory、9 (2): 129–135、doi : 10.1016/S0021-9800(70)80019-9、MR 0262097。
Cvetković, Dragoš; Rowlinson, Peter; Simić, Slobodan (2004)、「線グラフのスペクトル一般化」、ロンドン数学会講義ノートシリーズ、第314巻、ケンブリッジ：ケンブリッジ大学出版局、doi :10.1017/CBO9780511751752、ISBN 0-521-83663-8、MR 2120511。
Degiorgi, Daniele Giorgio; Simon, Klaus (1995)、「線グラフ認識のための動的アルゴリズム」、Graph-theoretic concepts in computer science (Aachen, 1995)、Lecture Notes in Computer Science、vol. 1017、ベルリン: Springer、pp. 37–48、doi :10.1007/3-540-60618-1_64、MR 1400011。
エヴァンス、TS; ランビオッテ、R. (2009)、「線グラフ、リンクパーティション、重複コミュニティ」、Physical Review E、80 (1): 016105、arXiv : 0903.2181、Bibcode :2009PhRvE..80a6105E、doi :10.1103/PhysRevE.80.016105、PMID 19658772。
エヴァンス、TS; ランビオッテ、R. (2010)、「重複コミュニティの重み付きネットワークの線グラフ」、ヨーロッパ物理ジャーナル B、77 (2): 265–272、arXiv : 0912.4389、Bibcode :2010EPJB...77..265E、doi :10.1140/epjb/e2010-00261-8、S2CID 119504507。
グリーンウェル、DL; ヘミンガー、ロバート L. (1972)、「平面線グラフのグラフの禁止部分グラフ」、離散数学、2 :31–34、doi : 10.1016/0012-365X(72)90058-1、MR 0297604。
ハラリー、F . Norman、RZ (1960)、「線ダイグラフのいくつかのプロパティ」、Rendiconti del Circolo Matematico di Palermo、9 (2): 161–169、doi :10.1007/BF02854581、hdl : 10338.dmlcz/128114、S2CID 122473974。
Harary, F. (1972)、「8. 線グラフ」、グラフ理論(PDF) 、マサチューセッツ州: Addison-Wesley、pp. 71–83、2017-02-07にオリジナル(PDF)からアーカイブ、 2013-11-08 に取得。
Hemminger, RL; Beineke, LW (1978)、「線グラフと線有向グラフ」、Beineke, LW; Wilson, RJ (編)、『グラフ理論の厳選トピック』、Academic Press Inc.、pp. 271–305。
Jung、HA (1966)、「Zu einem Isomorphiesatz von H. Whitney für Graphen」、Mathematische Annalen (ドイツ語)、164 (3): 270–271、doi :10.1007/BF01360250、MR 0197353、S2CID 119898359。
Krausz, J. (1943)、「ホイットニーの新理論のデモ」、Mat.フィズ。ラポック、50 : 75–85、MR 0018403。
Lehot, Philippe GH (1974)、「線グラフを検出してそのルートグラフを出力するための最適なアルゴリズム」、Journal of the ACM、21 (4): 569–575、doi : 10.1145/321850.321853、MR 0347690、S2CID 15036484。
マフレー、フレデリック (1992)、「完璧な線グラフのカーネル」、組み合わせ理論ジャーナル、シリーズ B、55 (1): 1–8、doi : 10.1016/0095-8956(92)90028-V、MR 1159851。
Metelsky, Yury; Tyshkevich, Regina (1997)、「線形 3 ユニフォームハイパーグラフの線グラフについて」、Journal of Graph Theory、25 (4): 243–251、doi :10.1002/(SICI)1097-0118(199708)25:4<243::AID-JGT1>3.0.CO;2-K。
Ramezanpour, A.; Karimipour, V.; Mashaghi, A. (2003)、「無相関ネットワークから相関ネットワークを生成する」、Phys. Rev. E、67 (4): 046107、arXiv : cond-mat/0212469、Bibcode :2003PhRvE..67d6107R、doi :10.1103/physreve.67.046107、PMID 12786436、S2CID 33054818。
ヴァン・ローイ、ACM。Wilf, HS (1965)、「有限グラフの交換グラフ」、Acta Mathematica Hungarica、16 (3–4): 263–269、doi : 10.1007/BF01904834、hdl : 10338.dmlcz/140421、S2CID 122866512。
Roussopoulos, ND (1973)、「線グラフGからグラフH を決定するための最大 { m , n } アルゴリズム」、Information Processing Letters、2 (4): 108–112、doi :10.1016/0020-0190(73)90029-X、MR 0424435。
リャチェク、ズデニェク; Vrána、Petr (2011)、「マルチグラフの折れ線グラフと爪のないグラフのハミルトン接続性」、Journal of Graph Theory、66 (2): 152–173、doi :10.1002/jgt.20498、MR 2778727、S2CID 8880045。
Sedláček, J. (1964)、「交換グラフのいくつかの特性」、グラフの理論とその応用 (Proc. Sympos. Smolenice、1963)、Publ. House Czechoslovak Acad. Sci.、プラハ、pp. 145–150、MR 0173255。
Sysło, Maciej M. (1982)、「線分有向グラフを認識してそのルートグラフを出力するラベル付けアルゴリズム」、Information Processing Letters、15 (1): 28–30、doi :10.1016/0020-0190(82)90080-1、MR 0678028。
Trotter, LE Jr. (1977)、「Line perfect graphs」、Mathematical Programming、12 (2): 255–259、doi :10.1007/BF01593791、MR 0457293、S2CID 38906333。
de Werra, D. (1978)、「オンライン完全グラフ」、数学プログラミング、15 (2): 236–238、doi :10.1007/BF01609025、MR 0509968、S2CID 37062237。
ホイットニー、H. (1932)、「合同グラフとグラフの連結性」、アメリカ数学誌、54 (1): 150–168、doi :10.2307/2371086、hdl : 10338.dmlcz/101067、JSTOR 2371086。
張、富吉。 Lin、Guo Ning (1987)、「On the de Bruijn–Good charts」、Acta Math。中国、30 (2): 195–205、MR 0891925。
Зверович、И。 Э。 (1997)、 Аналог теоремы Уитни для реберных графов мультиграфов и реберные мультиграфы、Diskretnaya Matematika (ロシア語)、9 (2): 98–105、doi : 10.4213/dm478、MR 1468075英語に翻訳すると、Zverovich, I. È. (1997)、「マルチグラフのエッジグラフとエッジマルチグラフに対するホイットニー定理の類似物」、離散数学と応用、7 (3): 287–294、doi :10.1515/dma.1997.7.3.287、S2CID 120525090となります。。

外部リンク

折れ線グラフ、グラフクラスの包含に関する情報システム
Weisstein、Eric W.「折れ線グラフ」。MathWorld。

[FOOTNOTEHemmingerBeineke1978273-1] ヘミンガー＆ベイネケ（1978）、273ページ。

[h72-71-2] Harary (1972)、71ページ。

[whitney-3] Whitney (1932); Krausz (1943); Harary (1972)、定理8.3、p. 72。Hararyは、Jung (1966)によるこの定理の簡略化された証明を与えている。

[paschos-4] Paschos, Vangelis Th. (2010)、組み合わせ最適化と理論計算機科学：インターフェースと展望、John Wiley & Sons、p. 394、ISBN 9780470393673明らかに、グラフのマッチングとその線グラフの独立集合の間には 1 対 1 の対応があります。

[5] 線グラフの接続性を考慮する際に孤立した頂点を考慮する必要があることは、Cvetković、Rowlinson、Simić (2004)、32 ページで指摘されています。

[6] Harary (1972)、定理 8.1、p. 72.

[7] Diestel, Reinhard (2006)、グラフ理論、Graduate Texts in Mathematics、vol. 173、Springer、p. 112、ISBN 9783540261834無料オンライン版の第 5 章 (「カラーリング」)、118 ページにも掲載されています。

[8] ラウリ、ヨゼフ、スカペラート、ラファエレ (2003)、「グラフ自己同型と再構築に関するトピック」、ロンドン数学会学生テキスト、第 54 巻、ケンブリッジ: ケンブリッジ大学出版局、p. 44、ISBN 0-521-82151-7、MR 1971819ラウリとスカペラートはこの結果をマーク・ワトキンスに帰した。

[9] Harary (1972)、定理 8.8、p. 80.

[FOOTNOTERamezanpourKarimipourMashaghi2003-10] ラメザンプール、カリミプール、マシャギ (2003)。

[11] ユング (1966);デジョルジとサイモン (1995)。

[z97-12] アブ・ズヴェロヴィッチ（1997）

[13] van Dam, Edwin R.; Haemers, Willem H. (2003)、「どのグラフがそのスペクトルによって決定されるか?」、線形代数とその応用、373 : 241–272、doi : 10.1016/S0024-3795(03)00483-X、MR 2022290、S2CID 32070167特に命題8（262ページ）を参照。

[14] Harary (1972)、定理8.6、p. 79。Hararyはこの結果を、LC Chang (1959)とAJ Hoffman (1960)による独立した論文によるものとしている。

[15] マリア・チュドノフスキー、ニール・ロバートソン、ポール・シーモア、ロビン・トーマス(2006)、「強い完全グラフ定理」、数学年報、164 (1): 51–229、arXiv : math/0212070、doi :10.4007/annals.2006.164.51、S2CID 119151552. Roussel, F.、Rusu, I.、Thuillier, H. (2009)、「強い完全グラフ予想: 40 年間の試みとその解決」、Discrete Mathematics、309 (20): 6092–6113、doi : 10.1016/j.disc.2009.05.024、MR 2552645、S2CID 16049392も参照。。

[16] Harary (1972)、定理 8.7、p. 79。Harary は、完全二部グラフの線グラフのこの特徴付けを Moon と Hoffman に帰した。両側の頂点の数が等しいケースは、以前に Shrikhande によって証明されていた。

[17] トロッター (1977);デ・ウェラ (1978)。

[FOOTNOTEMaffray1992-18] マフレー（1992年）。

[FOOTNOTETrotter1977-19] トロッター（1977年）。

[h72-8.4-20] Harary (1972)、定理 8.4、p. 74 では、線グラフの 3 つの同等な特徴付けが示されています。それは、辺をクリークに分割すること、クローフリーで奇数のダイヤモンドフリーである性質、および Beineke の 9 つの禁制グラフです。

[21] サムナー、デイビッド・P. (1974)、「1因子グラフ」、アメリカ数学会紀要、42 (1)、アメリカ数学会: 8–12、doi :10.2307/2039666、JSTOR 2039666、MR 0323648。Las Vergnas, M. (1975)、「グラフのマッチングに関するメモ」、Cahiers du Centre d'Études de Recherche Opérationnelle、17 (2–3–4): 257–260、MR 0412042。

[22] Harary (1972)、定理8.5、p. 78。Hararyはこの結果をGary Chartrandに帰している。

[23] エルデシュ、ポール;サックス、マイケル;ソス、ヴェラ T. (1986)、「グラフの最大誘導木」、Journal of Combinatorial Theory、シリーズ B、41 (1): 61–79、doi : 10.1016/0095-8956(86)90028-6。

[FOOTNOTECvetkovićRowlinsonSimić2004-24] ツヴェトコビッチ、ローリンソン、シミッチ (2004)。

[mt97-25] メテルスキー＆ティシュケビッチ（1997）

[26] この結果はHarary (1972)の定理8.2でもある。

[27] Harary (1972)、定理8.11、p. 81。Hararyはこの結果をGary Chartrandに帰している。

[28] セドラチェク (1964);グリーンウェルとヘミンジャー (1972)。

[29] アーチディーコン、ダン（1992）、「メディアルグラフと電圧-電流双対性」、離散数学、104（2）：111–141、doi：10.1016/0012-365X（92）90328-D、MR 1172842。

[30] McKee, TA (1989)、「地理的双対性のグラフ理論モデル」、Combinatorial Mathematics: Proceedings of the Third International Conference (New York, 1985)、Ann. New York Acad. Sci.、vol. 555、ニューヨーク: New York Acad. Sci.、pp. 310–315、Bibcode :1989NYASA.555..310M、doi :10.1111/j.1749-6632.1989.tb22465.x、MR 1018637、S2CID 86300941。

[31] ピュー、アンソニー（1976）、多面体：視覚的アプローチ、カリフォルニア大学出版局、ISBN 9780520030565。

[32] ローブ、アーサー・リー（1991）、空間構造—その調和と対位法（第5版）、ビルクハウザー、ISBN 9783764335885。

[33] Weisstein, Eric W.「Rectification」。MathWorld。

[34] ハラリー（1972）、82ページ。

[FOOTNOTERyjáčekVrána2011-35] Ryjáček & Vrána (2011).

[FOOTNOTEHararyNorman1960-36] ハラリー＆ノーマン（1960年）。

[FOOTNOTEZhangLin1987-37] 張・林（1987年）。

[FOOTNOTEEvansLambiotte2009-38] エヴァンス＆ランビオット（2009年）。

[FOOTNOTEEvansLambiotte2010-39] エヴァンス＆ランビオット（2010年）。

[40] Meshulam, Roy (2001-01-01). 「クリーク複合体とハイパーグラフマッチング」. Combinatorica . 21 (1): 89–94. doi :10.1007/s004930170006. ISSN 1439-6912. S2CID 207006642.