Solution to a Conjecture on the Permanental Sum

Autor:	Tingzeng Wu, Xueji Jiu
Jazyk:	angličtina
Rok vydání:	2024
Předmět:	permanental sum Hosoya index graph operation extremal graph Mathematics QA1-939
Zdroj:	Axioms, Vol 13, Iss 3, p 166 (2024)
Druh dokumentu:	article
ISSN:	2075-1680
DOI:	10.3390/axioms13030166
Popis:	Let G be a graph with n vertices and m edges. A(G) and I denote, respectively, the adjacency matrix of G and an n by n identity matrix. For a graph G, the permanent of matrix (I+A(G)) is called the permanental sum of G. In this paper, we give a relation between the Hosoya index and the permanental sum of G. This implies that the computational complexity of the permanental sum is NP-complete. Furthermore, we characterize the graphs with the minimum permanental sum among all graphs of n vertices and m edges, where n+3≤m≤2n−3.
Databáze:	Directory of Open Access Journals
Externí odkaz:	https://doaj.org/article/244d2d2d642b4a3bbf76ee3d713ba9e5 Zobrazit plný text záznamu View record in DOAJ Plný text ve formátu PDF Plný text ve formátu HTML
Nepřihlášeným uživatelům se plný text nezobrazuje	K zobrazení výsledku je třeba se přihlásit.