Chulalongkorn University Theses and Dissertations (Chula ETD)

Graphs whose square is panconnected

Other Title (Parallel Title in Other Language of ETD)

กราฟที่กำลังสองมีสมบัติเชื่อมโยงรวม

Year (A.D.)

2010

Document Type

Thesis

First Advisor

Wanida Hemakul

Second Advisor

Gek Ling Chia

Faculty/College

Faculty of Science (คณะวิทยาศาสตร์)

Degree Name

Doctor of Philosophy

Degree Level

Doctoral Degree

Degree Discipline

Mathematics

DOI

10.58837/CHULA.THE.2010.1144

Abstract

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.

Other Abstract (Other language abstract of ETD)

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

Link to Full Text

Share

COinS