Edinburgh Research Explorer

Order of the largest Sachs subgraphs in graphs

Research output: Contribution to journalArticle

Original languageEnglish
Pages (from-to)204-209
Number of pages5
JournalLinear and Multilinear Algebra
Volume65
Issue number1
Early online date5 May 2016
DOIs
Publication statusPublished - 2017

Abstract

Let G be a graph. A subgraph H of G is called a Sachs subgraph if each component of H is either a copy of K2 or a 2-regular subgraph of G. The order of the largest Sachs subgraph of G is called the perrank of G. A graph G of order n has full perrank if perrank (G) = n. In this article, we characterize the family of all graphs of order n whose permanents of their adjacency matrices are 1. Then we prove that the line graph of G, L(G), has full perrank, unless G is isomorphic to some special trees.

ID: 42857157