Characterization and Power GraphsWe

Characterization and Power Graphs
We first introduce the concept of a power graph.
Definition 2.1 Let k be a positive integer. The power of a graph Gk of G has V (Gk) = V (G) and two vertices u and v in Gk are adjacent in Gk whenever d(u, v) ≤ k in G.
Now, for avery pair of positive integers n and k, Knk = Kn. Hence, the two admit equal tree covering number.
The following result follows immediately from the definition of a power graph.
Theorem 2.2 Let G be a nontrivial connected graph with d(G) = k, then tc(G) = tc(Kn).
Here, we characterized graphs with tree covering number equal to 2.
Theorem 2.3 Let G be a non trivial connected graph, then tc(G) = 2 if and only if G is a connected graph having a cycle and an acyclic subgraph H such that E(G)E(H) is a tree.
Proof : Suppose that tc(G) = 2 and let FG = {G1, G2}, then G1 is a tree. This implies that E(G)E(G1) = E(G2), hence GG1 = G2 and G2 is a tree. Conversely, suppose that G is a connected graph having a cycle and an acyclic subgraph H such that E(G)E(H) is a tree. Let G1 = H and G2 = G E(H). Then FG = {G1, G2} is a tree cover G. Hence tc(G) ≤ |FG| = 2. Accordingly tc(G) = 2.

ผลลัพธ์ (ไทย) 1:

คุณลักษณะและกราฟพลังงานเราแนะนำแนวคิดของกราฟพลังงานก่อน2.1 กำหนดให้ k เป็นจำนวนเต็มบวก อำนาจของกราฟ Gk G ได้ V (Gk) = V (G) และสองจุดยอด u และ v ใน Gk อยู่ติดกันใน Gk เมื่อ d (u, v) ≤ k ในกรัมตอนนี้ สำหรับคู่ avery ของจำนวนเต็มบวก n และ k, Knk = Kn. ดังนั้น ทั้งสองยอมรับครอบคลุมหมายเลขต้นไม้เท่านั้นผลลัพธ์ต่อไปนี้ตามคำนิยามของกราฟพลังงานทันทีทฤษฎีบทที่ 2.2 ให้ G เป็นกราฟเชื่อมต่อ nontrivial กับ d(G) = k แล้ว tc(G) = tc(Kn)ที่นี่ เราลักษณะกราฟกับต้นไม้ที่ครอบคลุมจำนวนเท่ากับ 2ทฤษฎีบทที่ 2.3 ให้ G เป็นกราฟเชื่อมต่อไม่ใช่เล็กน้อย แล้ว tc(G) = 2 ถ้าและเฉพาะถ้า G เป็นกราฟเชื่อมโยงที่มีวงจรและการ subgraph acyclic H ที่เป็น E(G)E(H)หลักฐาน: สมมติว่า tc(G) = 2 และให้ FG = {G1, G2 }, แล้ว G1 เป็นต้นไม้ หมายความที่ E(G)E(G1) = E(G2) ดังนั้น GG1 = G2 G2 เป็น ต้นไม้ ในทางกลับกัน สมมติว่า G เป็นกราฟเชื่อมต่อที่มีวงจรและการ subgraph acyclic H ที่เป็น E(G)E(H) ให้ G1 = H และ G2 = G E(H) แล้ว FG = {G1, G2 } เป็นฝาครอบต้นไม้กรัม Hence tc(G) ≤ | FG| = 2 ดังนั้น tc(G) = 2