Đang chuẩn bị liên kết để tải về tài liệu:
Báo cáo toán học: "The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements"
Đang chuẩn bị nút TẢI XUỐNG, xin hãy chờ
Tải xuống
Tuyển tập các báo cáo nghiên cứu khoa học trên tạp chí toán học quốc tế đề tài: The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements. | The characteristic polynomial of a graph is reconstructible from the characteristic polynomials of its vertex-deleted subgraphs and their complements Elias M. Hagos emhagos@hotmail.com Submitted June 10 1999 Accepted February 13 2000. Abstract The question of whether the characteristic polynomial of a simple graph is uniquely determined by the characteristic polynomials of its vertex-deleted subgraphs is one of the many unresolved problems in graph reconstruction. In this paper we prove that the characteristic polynomial of a graph is reconstructible from the characteristic polynomials of the vertex-deleted subgraphs of the graph and its complement. AMS Classification Numbers 05C60 05C50 1 Introduction Let G V E be a simple graph with a vertex set of at least three elements V 1 . ng. We denote by E G the set of its edges. A subgraph of G obtained by deleting vertex i and all its incident edges is called a vertex-deleted subgraph of G and is denoted by Gj. The collection of vertex-deleted subgraphs of G is known as its deck. The characteristic polynomial of G is the characteristic polynomial of its adjacency matrix A and is defined by PG x det xI A . We call the collection of the characteristic polynomials of the vertex-deleted subgraphs the polynomial deck of G and denote it by P G PG1 PG2 . PGng. In general a property of a graph is said to be reconstructible if it is uniquely determined by its deck. Tutte 11 proved that the characteristic polynomial of a graph is reconstructible from its deck. But is the full knowledge of the vertex-deleted subgraphs necessary to reconstruct the characteristic polynomial Gutman and Cvetkovic 6 first raised the still unresolved question 1 2 THE ELECTRONIC JOURNAL OF COMBINATORICS 7 2000 R12 of whether the polynomial deck of a simple graph on at least three vertices contains enough information to reconstruct its characteristic polynomial. Some results are reported in 2 8 10 . In this paper we prove that PG x is uniquely determined .