Fukuoka Institute of Technology REPOSITORY SYSTEM

HOME    repository info    mypage        Japanese    library    university    Feedback

Fukuoka Institute of Technology Repository >
02.University Bulletins & Report >
Vol.52.No.1(81) >

Title :極大平面的グラフの同サイズの2つの木と連結成分に対する構成可能性に関する考察
Authors :高橋 昌也
タカハシ マサヤ
Issue Date :Sep-2019
Abstract :For any integer n≧3, let G be the maximal planar graph with n vertices and m=3n−6 edges, and, T1 and T2 be any two trees with n−1 vertices and n−2 edges each other. If G contains T1 and T2 then we define the following subgraphs G′ and G″ of G as follows. Let G′ be a graph obtained by deleting edges of T1 and T2. Furthermore, let G″ be a graph obtained by deleting isolate vertices of G′. In this paper, we consider the problem to determine whether there is a maximal planar graph G such that T1 and T2 are contained in G and G″ is simple and connected subgraph with n−2 edges obtained from G, in the 3≦n≦7 case. As a conclusion, we can obtain that the answer of the problem is “yes”. In this paper, we discuss the detail of our consideration as the following ⑴ and ⑵. ⑴ If n=7, T1 and T2 are star type trees as table 3.8 described below, and G is the maximal planar with 7 vertices and 15 edges as table 4.6 described below, then G can not contain T1 and T2 in the same time. ⑵ Otherwise, G can contain T1 and T2, and G″ which is simple and connected subgraph with n−2 edges obtained from G.
Type Local :紀要論文
ISSN :02876620
Publisher :福岡工業大学附属図書館
URI :http://hdl.handle.net/11478/1367
citation :福岡工業大学研究論集
Citation :福岡工業大学研究論集 Vol.52 no.1 p.31 -50
Appears in Collections:Vol.52.No.1(81)

Files in This Item:

File Description SizeFormat
11478-1367_p31.pdf1569KbAdobe PDFView/Open