完整後設資料紀錄
DC 欄位語言
dc.contributor.authorKao, Shin-Shinen_US
dc.contributor.authorLin, Cheng-Kuanen_US
dc.contributor.authorHuang, Hua-Minen_US
dc.contributor.authorHsu, Lih-Hsingen_US
dc.date.accessioned2019-04-02T05:58:12Z-
dc.date.available2019-04-02T05:58:12Z-
dc.date.issued2012-07-01en_US
dc.identifier.issn0381-7032en_US
dc.identifier.urihttp://hdl.handle.net/11536/150471-
dc.description.abstractA graph G is pancyclic if it contains a cycle of every length from 3 to vertical bar V(G)vertical bar inclusive. A graph G is panconnected if there exists a path of length l joining any two different vertices x and y with d(G)(x,y) <= l <= vertical bar V(G)vertical bar - 1, where d(G)(x,y) denotes the distance between x and y in G. A hamiltonian graph G is panpositionable if for any two different vertices x and y of G and any integer k with d(G)(x,y) <= k <= vertical bar V(G)vertical bar/2, there exists a hamiltonian cycle C of G with d(C)(x,y) = k, where d(C)(x,y) denotes the distance between x and y in a hamiltonian cycle C of G. It is obvious that panconnected graphs are pancyclic, and panpositionable graphs are pancyclic. The above properties can be studied in bipartite graphs after some modification. A graph H = (V-0 boolean OR V-1, E) is bipartite if V(H) = V-0 boolean OR V-1 and E(H) is a subset of {(u, v) vertical bar u is an element of V-0, v is an element of V-1}. A graph is bipancyclic if it contains a cycle of every even length from 4 to 2 . left perpendicular vertical bar V(H)vertical bar/2right perpendicular inclusive. A graph H is bipanconnected if there exists a path of length 1 joining any two different vertices x and y with d(H)(x,y) <= l <= vertical bar V(H)vertical bar - 1, where d(H)(x, y) denotes the distance between x and y in H and 1 dH(x,y) is even. A hamiltonian graph H is bipanpositionable if for any two different vertices x and y of H and for any integer k with d(H)(x,y) <= k < vertical bar V(H)vertical bar/2, there exists a hamiltonian cycle C of H with d(G)(x,y) = k, where d(G)(x,y) denotes the distance between x and y in a hamiltonian cycle C of H and k - d(H)(x,y) is even. It can be shown that bipanconnected graphs are bipancyclic, and bipanpositionable graphs are bipancyclic. In this paper, we present some examples of pancyclic graphs that are neither panconnected nor panpositionable, some examples of panconnected graphs that are not panpositionable, and some examples of graphs that are panconnected and panpositionable, for nonbipartite graphs. Corresponding examples for bipartite graphs are discussed. The existence of panpositionable (or bipanpositionable, resp.) graphs that are not panconnected (or bipanconnected, resp.) is still an open problem.en_US
dc.language.isoen_USen_US
dc.subjectHamiltonianen_US
dc.subjectpancyclicen_US
dc.subjectpanconnecteden_US
dc.subjectpanpositionableen_US
dc.titlePancyclicity, Panconnectivity, and Panpositionability for General Graphs and Bipartite Graphsen_US
dc.typeArticleen_US
dc.identifier.journalARS COMBINATORIAen_US
dc.citation.volume105en_US
dc.citation.spage231en_US
dc.citation.epage246en_US
dc.contributor.department資訊工程學系zh_TW
dc.contributor.departmentDepartment of Computer Scienceen_US
dc.identifier.wosnumberWOS:000306871400022en_US
dc.citation.woscount4en_US
顯示於類別:期刊論文