tailieunhanh - Báo cáo tin học: "Nonexistence of triples of nonisomorphic connected graphs with isomorphic connected P3-graphs"

Tuyển tập các báo cáo nghiên cứu khoa học về toán học trên tạp chí toán học quốc tế đề tài: Nonexistence of triples of nonisomorphic connected graphs with isomorphic connected P3-graphs. | Nonexistence of triples of nonisomorphic connected graphs with isomorphic connected P3-graphs Xueliang Li and Yan Liu Center for Combinatorics and LPMC Nankai University Tianjin 300071 China lxl@ liuyanday@ Submitted Aug 21 2006 Accepted Feb 3 2008 Published Feb 11 2008 Mathematics Subject Classifications 05C60 05C75 Abstract In the paper Broersma and Hoede Path graphs J. Graph Theory 13 1989 427-444 the authors asked a problem whether there is a triple of mutually nonisomorphic connected graphs which have an isomorphic connected Fa-graph. In this paper we show that there is no such triple and thus completely solve this problem. Keywords path graph connected isomorphism 1 Introduction Broersma and Hoede 3 generalized the concept of line graphs to that of path graphs by defining adjacency as follows. Let k be a positive integer and Pk and Ck denote a path and a cycle with k vertices respectively. Let nk G be the set of all Pk s in G. The path graph Pk G of G is a graph with vertex set nk G in which two Pk s are adjacent whenever their union is a path Pk 1 or a cycle Ck. Broersma and Hoede got many results on P3-graphs and in particular described two infinite classes of pairs of nonisomorphic connected graphs which have isomorphic connected P3-graphs. They also raised a number of unsolved problems or questions most of which have been solved in the intervening years. Only the following one remains unanswered. Problem. Does there exist a triple of mutually nonisomorphic connected graphs which have an isomorphic connected P3-graph Research supported by PCSIRT NSFC and the 973 program. THE ELECTRONIC JOURNAL OF COMBINATORICS 15 2008 R31 1 For k 2 . line graphs from Whitney s result see 4 it is not difficult to see that the problem has a negative answer. In 5 the authors showed that for k 4 there are not only triples of but also arbitrarily many mutually nonisomorphic connected graphs with isomorphic connected Pk-graphs. Interestingly however .