LCF表記

数学のグラフ理論の分野において、LCF表記法またはLCFコードは、ジョシュア・レーダーバーグによって考案され、HSM・コクセターとロバート・フルヒトによって拡張された、ハミルトン閉路を含む立方グラフの表現法である。^[2]^{[3]閉路自体は各}頂点の3つの隣接点のうち2つを含み、LCF表記法は各頂点の3番目の隣接点が閉路のどのくらい上に存在するかを指定する。1つのグラフは、LCF表記法で複数の異なる表現を持つことができる。

説明

ハミルトングラフでは、頂点はサイクルに配置でき、頂点ごとに 2 つの辺が存在する。各頂点からの 3 番目の辺は、時計回り (正) または反時計回り (負) に何番目の位置につながるかで記述できる。LCF 表記法の基本形式は、任意に選択された頂点から始まり、角括弧で囲まれたこれらの位置の数のシーケンスである。括弧内の数字は、頂点の数をNとして解釈される。N を法 として0、1、または N − 1 と同値のエントリは、この数列には現れない^{[4] 。これは、それらが}ループまたは多重隣接に対応するためであり、どちらも単純なグラフでは許可されていない。

パターンは繰り返されることが多く、繰り返しの回数は表記法の上付き文字で示すことができます。たとえば、右に示すナウルグラフ^{[1]には、同じ 6 つのオフセットが 4 回繰り返されており、LCF 表記法 [5, −9, 7, −7, 9, −5]}⁴で表すことができます。ハミルトン閉路と開始頂点の選択によっては、1 つのグラフに複数の異なる LCF 表記法が使用される場合があります。

アプリケーション

LCF表記法は、以下の例のようにハミルトン立方グラフの簡潔な記述を公開する際に役立ちます。さらに、グラフを操作するためのソフトウェアパッケージの中には、LCF表記法からグラフを作成するためのユーティリティが含まれているものもあります。^[5]

グラフがLCF表記法で表現されている場合、グラフが二部グラフであるかどうかをテストするのは簡単です。これは、LCF表記法のすべてのオフセットが奇数である場合にのみ当てはまります。^[6]

例

拡張LCF表記

LCF表記のより複雑な拡張版は、後の研究でコクセター、フルクト、パワーズによって提供された。^[8]特に、彼らは「反回文」表記を導入した。つまり、角括弧内の数字の後半が前半の逆で、すべての符号が入れ替わっている場合は、セミコロンとダッシュに置き換えられる。ナウルグラフは[5, −9, 7, −7, 9, −5] ⁴でこの条件を満たしており、拡張表記では[5, −9, 7; −] ⁴と書くことができる。 ^[9]

参考文献

^ ab Eppstein, D.、「ナウルグラフの多くの側面」、2007年。
^ Pisanski, Tomaž ; Servatius, Brigitte (2013)、「2.3.2 立方グラフと LCF 表記法」、Configurations from a Graphical Viewpoint、Springer、p. 32、ISBN 9780817683641。
^ Frucht, R. (1976)、「三価ハミルトングラフの標準表現」、Journal of Graph Theory、1 (1): 45–60、doi :10.1002/jgt.3190010111、MR 0463029。
^ クトナー、クラウディヤ;マルシッチ、ドラガン(2008)、「次数 $4$ $p$ の頂点推移グラフのハミルトニシティ」、European Journal of Combinatorics、29 (2): 423–438、arXiv : math/0606585、doi :10.1016/j.ejc.2007.02。 002、MR 2388379セクション2を参照してください。
^ 例: Maple、NetworkX Archived 2012-03-02 at the Wayback Machine、igraph、sage。
^ コクセター、ハロルド・スコット・マクドナルド;フルクト、ロベルト; パワーズ、デビッド・L. (1981)、ゼロ対称グラフ、Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]、ニューヨーク・ロンドン、p. 13、ISBN 0-12-194580-4、MR 0658666。
^ Coxeter、Frucht & Powers (1981)、図 1.1、p. 5.
^ Coxeter、Frucht & Powers (1981)、p. 54.
^ Coxeter、Frucht & Powers (1981)、p. 12.

外部リンク

Weisstein、Eric W.「LCF 表記法」。MathWorld。
Ed Pegg Jr. (2003年12月29日)、Math Games: Cubic Symmetric Graphs、Mathematical Association of America、2013年5月7日時点のオリジナルよりアーカイブ、 2010年9月25日閲覧。
「LCF 表記法による 3 次ハミルトングラフ」 – D3jsライブラリを使用して構築された JavaScript インタラクティブアプリケーション

[DE1-1] Eppstein, D.、「ナウルグラフの多くの側面」、2007年。

[2] Pisanski, Tomaž ; Servatius, Brigitte (2013)、「2.3.2 立方グラフと LCF 表記法」、Configurations from a Graphical Viewpoint、Springer、p. 32、ISBN 9780817683641。

[3] Frucht, R. (1976)、「三価ハミルトングラフの標準表現」、Journal of Graph Theory、1 (1): 45–60、doi :10.1002/jgt.3190010111、MR 0463029。

[4] クトナー、クラウディヤ;マルシッチ、ドラガン(2008)、「次数 $4$ $p$ の頂点推移グラフのハミルトニシティ」、European Journal of Combinatorics、29 (2): 423–438、arXiv : math/0606585、doi :10.1016/j.ejc.2007.02。 002、MR 2388379セクション2を参照してください。

[5] 例: Maple、NetworkX Archived 2012-03-02 at the Wayback Machine、igraph、sage。

[6] コクセター、ハロルド・スコット・マクドナルド;フルクト、ロベルト; パワーズ、デビッド・L. (1981)、ゼロ対称グラフ、Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers]、ニューヨーク・ロンドン、p. 13、ISBN 0-12-194580-4、MR 0658666。

[FOOTNOTECoxeterFruchtPowers1981Fig.&nbsp;1.1,_p.&nbsp;5-7] Coxeter、Frucht & Powers (1981)、図 1.1、p. 5.

[FOOTNOTECoxeterFruchtPowers198154-8] Coxeter、Frucht & Powers (1981)、p. 54.

[FOOTNOTECoxeterFruchtPowers198112-9] Coxeter、Frucht & Powers (1981)、p. 12.