リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

リケラボ 全国の大学リポジトリにある学位論文・教授論文を一括検索するならリケラボ論文検索大学・研究所にある論文を検索できる

大学・研究所にある論文を検索できる 「Embedding optimization problems for a graph related to Laplacian eigenvalue maximization」の論文概要。リケラボ論文検索は、全国の大学リポジトリにある学位論文・教授論文を一括検索できる論文検索サービスです。

コピーが完了しました

URLをコピーしました

論文の公開元へ論文の公開元へ
書き出し

Embedding optimization problems for a graph related to Laplacian eigenvalue maximization

Gomyou, Takumi 五明, 工 名古屋大学

2020.04.02

概要

Goring-Helmberg-Wapplerによって有限グラフのユークリッド空間への埋め込みに関する最適化問題が導入された.その問題は,absolute algebraic connectivityと呼ばれる最適値を与えるラプラシアン最小正固有値の最大化問題の,半正値プログラミングの意味での双対問題として得られる.有限グラフG = (V,五)に対し,頂点上のパラメーター s G (R>0)'vlと辺上のパラメーター I G (R>0)IeIを与えたとき,それらの最適化問題はパラメーター s, I付きとして一般化される.Goringらは,一般化された埋め込み問題における最適埋め込みが実現できる空間の最小次元から rotational dimension を疋義した.rotational dimension (以下 rotdim(G)と記す)はグラフのマイナーによる順序列に対して単調に変化するグラフ不変量である. すなわちGf がG のマイナーであるならばrotdim( G) > rotdim( び) が成り立っ.

申請者は次の2つについての研究を行った.(i)頂点数の多い完全部分グラフを持つグラフのrotational dimensionの考察,(ii) Goringらによって導入された問題とは別の埋め込み問題に関する考察.

(i)完全グラフKnt、ら1辺を取り除いたグラフのrotational dimensionを決定することによって,rotational dimensionによる完全グラフの特徴付けを行った.

定理1.η頂点グラフGにおいて,G二Κηであることの必要十分条件はGの rotational dimensionがτι—1となることである.

また弦グラフと呼ばれる,その内部の長さ4以上の全ての閉路において,その閉路で隣接しないある2頂点が辺でつながれているようなグラフに着眼し,その rotational dimensionについても考察した.Goringらによる結果から rotational dimension は clique number やtree-widthといった別のグラフ不変量によって上下から評価されるが,Gが弦グラフのときこの両不等式はタイトなものになる.この弦グラフの性質を用いることによって,rotational dimensionを保ちつつ,頂点数の多い弦グラフを構成する方法を考案した.

(ii)有限グラフに対して,Goringらによるグラフ埋め込み問題とは別の埋め込み問題を導入した.以下パラメーター s,Iを固定M :=£.ev^とする.

Goringらによる埋め込み問題はラプラシアン最小正固有値の最大化問題と双対関係にあるが,我々の問題においても同様であることを明らかにした.

定理1.我々の埋め込み問題はラプラシアン最小正固有値の最大化問題の双対問題である.

さらに,様々な多面体に対して,その1-スケルトンと同型なグラフの最適埋め込みは,もとの多面体の1-スケルトンとして実現されることを確認した.例えば,フラーレングラフC60 の最適埋め込みは切頂20面体(サッカーボール)によって与えられる.

(ii)における結果は小林俊公氏,近藤剛史氏,納谷信氏との共同研究によるものである.

参考文献

[1] Bodlaender, H. L.: Some classes of graphs with bounded treewidth. Bull. EATCS 36, 116-126 (1988)

[2] Boyd, S. and Vandenberghe, L.: Convex optimization. Cambridge University Press (2004)

[3] Chartrand, G. and Harary, F.: Planar permutation graphs. Annales de l’I.H.P. Probabilit´es et statistiques. 3, 433-438 (1967)

[4] Chung, F. R. K., Kostant, B. and Sternberg, S.: Groups and the buckyball. Lie Theory and Geometry, Progress in Mathematics. 123, 97-126 (1994)

[5] Chung, F. R. K. and Mumford, D.: Chordal completions of planar graphs. J. Comb. Theory. 62(1), 96-106 (1994)

[6] Feit, W. and Higman, G.: The nonexistence of certain generalized polygons. J. Algebra. 1, 114-131 (1964)

[7] Fiedler, M.: Laplacian of graphs and algebraic connectivity. Combinatorics and Graph Theory. 25, 57-70 (1989)

[8] Gomyou, T.: The rotational dimension of a graph containing a clique. Graphs and Combinatorics (2019) (under submission)

[9] Gomyou, T., Kobayashi, T., Kondo, T. and Nayatani, S.: Optimal embedding and spectral gap of a finite graph. arXiv:2002.03584v1 [math.CO] (2020)

[10] G¨oring, F., Helmberg, C. and Wappler, M.: Embedded in the shadow of the separator. SIAM J. Optim. 19(1), 472-501 (2008)

[11] G¨oring, F., Helmberg, C. and Wappler, M.: The rotational dimension of a graph. J. Graph Theory. 66(4), 283-302 (2011)

[12] Heggernes, P.: Treewidth, partial k-trees, and chordal graphs. Partial curriculum in INF334 - Advanced algorithmical techniques, Department of Informatics, University of Bergen, Norway (2005)

[13] Helmberg, C.: Semidefinite programming for combinatorial optimization. ZIBReport 00-34, Berlin (2000) Habilitationsschrift.

[14] Izeki, H. and Nayatani, S.: Combinatorial harmonic maps and discrete-group actions on Hadamard spaces. Geom. Dedicata. 114, 147-188 (2005)

[15] Ivrissimtzis, I. and Peyerimhoff, N.: Spectral representations of vertex transitive graphs, Archimedean solids and finite Coxeter groups. Groups, geometry, and dynamics. 7, 591-615 (2013)

[16] Kawarabayashi, K and Mohar, B.: Some recent progress and applications in graph minor theory. Graphs Combin. 23(1), 1-46 (2007)

[17] Koster, Arie M. C. A., Bodlaender, Hans L. and Hoesel, Stan P.M. van. Treewidth: Computational experiments. Electronic Notes in Discrete Mathematics. 8, 54-57 (2001)

[18] Padrol-Sureda, A. and Pfeifle, J.: Graph operations and Laplacian eigenpolytopes. VII Jornadas de Matem´atica Discreta y Algor´ıtmica, 505-516 (2010)

[19] Robertson, N., Seymour, P. and Thomas, R.: Quickly excluding a planar graph. J. Combin. Theory Ser. B. 62, 323-348 (1994)

[20] Roger A. Horn and Charles R. Johnson.: Matrix analysis. Cambridge University Press, Cambridge (1985)

[21] Van der Holst, H., Laurent, M. and Schrijver, A.: On a minor-monotone graph invariant. J. Comb. Theory. 65(2), 291-304 (1995)

[22] Van der Holst, H., Lov´asz, L. and Schrijver, A.: The Colin de Verdi`ere graph parameter. Graph Theory and Combinatorial Biology. 29-85. J´anos Bolyai Mathematical Society. Budapest (1999)

[23] Wagner, K.: Uber eine Eigenschaft der ebenen Komplexe. Math. Ann. 114, 570-590 (1937)

[24] Wappler, M.: On graph embeddings and a new minor monotone graph parameter associated with the algebraic connectivity of a graph. dissertation, Fakult¨at f¨ur Mathematik, Technische Universit¨at Chemnitz (2013)

参考文献をもっと見る

全国の大学の
卒論・修論・学位論文

一発検索!

この論文の関連論文を見る