کد مقاله کد نشریه سال انتشار مقاله انگلیسی نسخه تمام متن
421289 684181 2010 10 صفحه PDF دانلود رایگان
عنوان انگلیسی مقاله ISI
Torsion formulas for signed graphs
موضوعات مرتبط
مهندسی و علوم پایه مهندسی کامپیوتر نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
Torsion formulas for signed graphs
چکیده انگلیسی

Following our recent exposition on the algebraic foundations of signed graphs, we introduce bond (circuit) basis matrices for the tension (flow) lattices of signed graphs, and compute the torsions of such matrices and Laplacians. We present closed formulas for the torsions of the incidence matrix, the Laplacian, bond basis matrices, and circuit basis matrices. These formulas show that the torsions of all such matrices are powers of 2, and so imply that the matroids of signed graphs are representable over any field of characteristic not 2. A notable feature of using torsion is that the Matrix-Tree formula for ordinary graphs and Zaslavsky’s formula for unbalanced signed graphs are unified into one Matrix-Basis formula in terms of the torsion of its Laplacian matrix, rather than in terms of its determinant, which vanishes for an ordinary graph unless one row is deleted from the incidence matrix.

ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Discrete Applied Mathematics - Volume 158, Issue 11, 6 June 2010, Pages 1148–1157
نویسندگان
, ,