Polynomial reconstruction of signed graphs

被引：10

作者：

Simic, Slobodan K. ^{[1
,2
]}

Stanic, Zoran ^{[3
]}

机构：

[1] State Univ Novi Pazar, Vuka Karadzica Bb, Novi Pazar 36300, Serbia

[2] Math Inst SANU, Knez Mihailova 36, Belgrade 11000, Serbia

[3] Univ Belgrade, Fac Math, Studentski Trg 16, Belgrade 11000, Serbia

来源：

LINEAR ALGEBRA AND ITS APPLICATIONS | 2016年 / 501卷

关键词：

Signed graph; Characteristic polynomial; Eigenvalues; Unicyclic graph;

D O I：

10.1016/j.laa.2016.03.036

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

The reconstruction problem of the characteristic polynomial of graphs from their polynomial decks was posed in 1973. So far this problem is not resolved except for some particular cases. Moreover, no counterexample for graphs of order n > 2 is known. Here we put forward the analogous problem for signed graphs, and besides some general results, we resolve it within signed trees and unicyclic signed graphs, and also within disconnected signed graphs whose one component is either a signed tree or is unicyclic. A family of counterexamples that was encountered in this paper consists of two signed cycles of the same order, one balanced and the other unbalanced. (C) 2016 Elsevier Inc. All rights reserved.

引用

页码：390 / 408

页数：19

共 11 条

[1] [Anonymous], U BEOGRAD PUBL EL MF
[2] Combinatorial approach for computing the characteristic polynomial of a matrix
Belardo, Francesco
Li Marzi, Enzo M.
Simic, Slobodan K.
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 433 (8-10) : 1513 - 1523
[3] Biyikoglu T, 2011, ARS COMBINATORIA, V100, P421
[4] Coates C., 1959, IRE T CIRCUIT THEORY, V6, P170, DOI DOI 10.1109/TCT.1959.1086537
[5] Cvetkovi D. M., 1995, Spectra of Graphs: Theory and Applications
[6] On the reconstruction of the characteristic polynomial of a graph
Cvetkovic, D
[J]. DISCRETE MATHEMATICS, 2000, 212 (1-2) : 45 - 52
[7] Cvetkovic D., 1998, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Nat., Sci. Nat, V116, P91
[8] Sciriha I, 2003, UTILITAS MATHEMATICA, V64, P33
[9] Polynomial reconstruction and terminal vertices
Sciriha, I
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2002, 356 (1-3) : 145 - 156
[10] On the polynomial reconstruction of graphs whose vertex-deleted subgraphs have spectra bounded from below by-2
Simic, Slobodan K.
Stanic, Zoran
[J]. LINEAR ALGEBRA AND ITS APPLICATIONS, 2008, 428 (8-9) : 1865 - 1873

← 1 2 →