グラフ理論コミュのk-連結なグラフ上の最長パス

n頂点、k-連結なグラフにおける最長パスの長さの下界について、
何かしらの結果をご存じの方がいらっしゃいましたら教えて頂けないでしょうか。

ちなみに以下のような問題を考えております。

【問題】１からnまでの数を重複なく、かつ連続するニ数が倍数関係になるように
並べたときの最長の数列の長さをL(n)で表す。

例　n=10のとき(5,10,2,4,8,1,6,3,9)　L(10)=9,

nを大きくしていったとき、L(n)/nはどうなるか。

コメント(6)

最初
全て
最新の40件

[1] mixiユーザー 12月20日 22:45

役に立つ情報か分かりませんが、グラフの独立数をαとおいたときに、頂点数k(n+α-k)/α以上のサイクルがあるという予想が1976年にFouquet&Jolivetによって提起され、最近O,West,Wuらによってこの予想が肯定的に解決されたようです。

また、ごく最近ですが、任意の２頂点u,vに関して、それらを結ぶパスで頂点数が(k-1)(n-k)/α+k以上のものが存在するという定理を私と二人の共同研究者が証明しています。

[2] mixiユーザー 12月21日 00:29

Shinyaさん、

ホットな情報をありがとうございます。
本業の方からコメント頂けるとは恐縮です。

ただ上の問題に、この結果を応用するのは難しそうですね。
（αは素数のオーダーで増加するので）

nを無限大にとばせば、次数の小さい頂点（nと比べて十分に少ない）を取り除くことで、
kをいくらでも大きくできると思うので、適当なkに対し、定数cが存在して
「n頂点、k-連結なグラフにはn/cの長さのパスが存在する」
というような結果があればありがたいです。

直感としては、2-連結のグラフでもcは有限の値を取りそうなんですが。

[3] mixiユーザー 12月21日 11:28

2-連結の場合、電気力線みたいな形のグラフだと長いパスが作れませんね。

[4] mixiユーザー 12月21日 18:18

独立数を気にしないのであれば、完全二部グラフＫk,n-kがあまり長いパスを作れない例になっているかと思います。

[6] mixiユーザー 12月22日 11:53

ありがとうございます。

一般的なグラフの性質を足がかりにできるかと思ったのですが、
自然数が作るグラフの特徴をもっと調べる必要がありそうですね。

ログインすると、みんなのコメントがもっと見れるよ