TRULY NONTRIVIAL GRAPHOIDAL COVERS-I
0
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
A graphoidal cover of a graph G is a collection Ψ of non- trivial paths (not necessarily open) in G such that every vertex of G is an internal vertex of at most one path in Ψ and every edge of G is in exactly one path in Ψ. A graphoidal cover Ψ of G is a truly non- trivial graphoidal cover (TNT graphoidal cover) of G if every path in Ψ has length greater than 1. A graph G is a truly nontrivial graph (TNT graph) if it possesses a TNT graphoidal cover. In this paper we intend to answer the fundamental question "Does every graph possess a TNT graphoidal cover ?", raised by Fred Roberts in first author's thesis re- port. After exhibiting the fact that not every graph possesses a TNT graphoidal cover, we could obtain some forbidden structures for a graph to be a TNT graph. And in the quest to find graphs having a TNT graphoidal cover, we could identify certain classes of trees and unicyclic graphs which are TNT graphs.
Abstract
A graphoidal cover of a graph G is a collection Ψ of non- trivial paths (not necessarily open) in G such that every vertex of G is an internal vertex of at most one path in Ψ and every edge of G is in exactly one path in Ψ. A graphoidal cover Ψ of G is a truly non- trivial graphoidal cover (TNT graphoidal cover) of G if every path in Ψ has length greater than 1. A graph G is a truly nontrivial graph (TNT graph) if it possesses a TNT graphoidal cover. In this paper we intend to answer the fundamental question "Does every graph possess a TNT graphoidal cover ?", raised by Fred Roberts in first author's thesis re- port. After exhibiting the fact that not every graph possesses a TNT graphoidal cover, we could obtain some forbidden structures for a graph to be a TNT graph. And in the quest to find graphs having a TNT graphoidal cover, we could identify certain classes of trees and unicyclic graphs which are TNT graphs.
참고문헌 (19)
- B. D. Acharya, "Further results on domination in graphoidally covered graphs", AKCE Int. J. Graphs Comb, 4(2), pp.127~138 (2007)
- B. D. Acharya, "On graphs whose graphoidal dom-ination number is one", AKCE Int. J. Graphs Comb., 12(2-3), pp.133~140 (2015)
- B. Devadas Acharya, "Domination in graphoidal covers of a graph", Discrete Math., 206(1-3), pp.3~33 (1999)
- B. Devadas Acharya, "Graphoidal covers and graphoidal cov-ering number of a graph", Indian J. Pure Appl. Math., 18(10), pp.882~890 (1987)
- S. Arumugam, "Graph theory and its applications", pp.1~28 (1997), Tata McGraw-Hill
- S. Arumugam, "Bounds on graphoidal length of a graph", Electronic Notes in Discrete Mathematics, 53, pp.113~122 (2016)
- S. Arumugam, "Graphoidal bipartite graphs", Graphs Combin., 10(4), pp.305~310 (1994)
- S. Arumugam, "Graphs with unique minimum graphoidal cover", In-dian J. Pure Appl. Math., 25(11), pp.1147~1153 (1994)
- S. Arumugam, "Graphs whose acyclic graphoidal covering number is one less than its maximum degree", Discrete Math., 240(1-3), pp.231~237 (2001)
- S. Arumugam, "Acyclic graphoidal covers and path partitions in a graph", Discrete Math., 190(1-3), pp.67~77 (1998)
- G. Chartrand, "Graphs & digraphs", pp.2005, Chapman & Hall
- Purnima Gupta, "Certain Extensions of the Notion of Domination in Graphs", Depart-ment of Mathematics, pp.1998
- Frank Harary, "Graph theory" (1969), Addison-Wesley Publishing Co.
- C. Pakkiam, "On the graphoidal covering number of a graph", Indian J. Pure Appl. Math., 20(4), pp.330~333 (1989)
- P. S. K. Reddy, "Graphoidal signed graphs", Proceedings of the Jangjeon Mathematical Society(장전수학회 논문집), 17(1), pp.41~50 (2014), 장전수학회
- I. Sahul Hamid, "On label graphoidal covering number|I", Trans. Comb., 1(4), pp.25~33 (2012)
- Semigraphs and their applications. Report on the DST Project, "E. Sampathkumar", ~ (2000)
- P. TITUS, "THE DETOUR MONOPHONIC GRPHOIDAL COVERING NUMBER OF A GRAPH", Proceedings of the Jangjeon Mathematical Society(장전수학회 논문집), 19(1), pp.47~56 (2016), 장전수학회
- Douglas B. West, "Introduction to graph theory" (1996), Prentice Hall, Inc.