Graphs whose square is panconnected

• Main Author: Sirirat Singhun (Author)
• Other Authors: Wanida Hemakul (Contributor), Gek Ling Chia (Contributor), Chulalongkorn University. Faculty of Science (Contributor)
• Format: Book
• Published: Chulalongkorn University, 2013-07-04T03:22:50Z.
• Subjects: Thesis
• Online Access: http://cuir.car.chula.ac.th/handle/123456789/32791
• Other title: กราฟที่กำลังสองมีสมบัติเชื่อมโยงรวม
• Notes: http://cuir.car.chula.ac.th/handle/123456789/32791
• Keywords: Graph theory; Hamiltonian graph theory; ทฤษฎีกราฟ; ทฤษฎีกราฟแฮมิลตัน

Thesis (Ph.D.)--Chulalongkorn University, 2010

The square of a graph G is the graph obtained from G by adding edges joining those pairs of vertices whose distance from each other in G is two. A graph is panconnected if, between any pair of distinct vertices, it contains a path of each length at least the distance between the two vertices. If G is connected, the cyclomatic number of G is defined as (G)| - (G)| + 1. Chia et al. [4] has already characterized all graphs with cyclomatic number no more than one whose square is panconnected. In this thesis, we characterize all graphs with cyclomatic number two whose square is panconnected. We show that if G has cyclomatic number three and the square of G is panconnected, then G is one of the eight families of graphs. Three of these families of graphs are generalized to three larger families of graphs. Necessary and sufficient conditions for these three larger families of graphs to have panconnected square are determined.

กำลังสองของกราฟ G คือ กราฟที่ได้จากกราฟ G โดยการเติมเส้นเชื่อมระหว่างจุดยอดสองจุดใด ๆ ซึ่งมีระยะทางในกราฟ G เท่ากับสอง กราฟมีสมบัติเชื่อมโยงรวมถ้าระหว่างจุดยอดสองจุดใด ๆ ที่ต่างกัน จะมีวิถีแต่ละขนาดตั้งแต่ระยะทางระหว่างจุดยอดสองจุดนั้นขึ้นไป ถ้ากราฟ G เป็นกราฟเชื่อมโยง เรานิยามจำนวนไซโคมาติกของกราฟ G เท่ากับ (G)| - (G)| + 1 เชียและคณะ [4] ได้แสดงลักษณะกราฟทั้งหมดที่จำนวนไซโคมาติกของกราฟไม่เกินหนึ่งซึ่งกำลังสองของกราฟนั้นมีสมบัติเชื่อมโยงรวม ในวิทยานิพนธ์นี้ เราแสดงลักษณะกราฟทั้งหมดที่จำนวนไซโคมาติกของกราฟนั้นเท่ากับสองซึ่งกำลังสองของกราฟมีสมบัติเชื่อมโยงรวม เราแสดงว่า ถ้า กราฟ G มีจำนวนไซโคมาติกเท่ากับสามและกำลังสองของกราฟ G มีสมบัติเชื่อมโยงรวม แล้ว กราฟ G ต้องเป็นหนึ่งในวงศ์ของกราฟจำนวนแปดวงศ์ เราวางนัยทั่วไปสำหรับวงศ์เหล่านี้ของกราฟจำนวนสามวงศ์ให้เป็นวงศ์ที่ใหญ่กว่าของกราฟ เราตรวจ สอบเงื่อนไขจำเป็นและเพียงพอสำหรับวงศ์ที่ใหญ่กว่าของกราฟดังกล่าวจำนวนสามวงศ์ที่กำลังสองของกราฟมีสมบัติเชื่อมโยงรวม