The Determinant of the Adjacency Matrix of a Graph

Previous article Next article The Determinant of the Adjacency Matrix of a GraphFrank HararyFrank Hararyhttps://doi.org/10.1137/1004057PDFBibTexSections ToolsAdd to favoritesExport CitationTrack CitationsEmail SectionsAbout1 C. L. Coates, Flow graph solutions of linear algebraic equations, IRE Transactions on Circuit Theory, CT-6 (1959), 170–187 CrossrefGoogle Scholar2 Lothar Collatz and , Ulrich Sinogowitz, Spektren endlicher Grafen, Abh. Math. Sem. Univ. Hamburg, 21 (1957), 63–77 MR0087952 (19,443b) 0077.36704 CrossrefGoogle Scholar3 C. A. Desoer, The optimum formula for the gain of a flow graph or a simple derivation of Coates' formula, Proc. IRE, 48 (1960), 883–889 CrossrefISIGoogle Scholar4 Frank Harary, A graph theoretic method for the complete reduction of a matrix with a view toward finding its eigenvalues, J. Math. Phys., 38 (1959/1960), 104–111 MR0109793 (22:678) 0087.01701 CrossrefGoogle Scholar5 D. König, Theorie der endlichen und unendlichen Graphen, Leipzig, 1936, reprinted New York, 1950 0013.22803 Google Scholar6 G. Pólya and , G. Szegö, Aufgaben und Lehrsatze aus der Analysis, vol. 2, Berlin, 1925, reprinted New York, 1945; p. 98 Google Scholar Previous article Next article FiguresRelatedReferencesCited ByDetails Applications of the Harary-Sachs theorem for hypergraphsLinear Algebra and its Applications, Vol. 649 | 1 Sep 2022 Cross Ref Sensor Fault Detection and Isolation via Networked Estimation: Rank-Deficient Dynamical SystemsInternational Journal of Control | 24 August 2022 Cross Ref On the adjacency matrix of a complex unit gain graphLinear and Multilinear Algebra, Vol. 70, No. 9 | 12 June 2020 Cross Ref Deep learning in the COVID-19 epidemic: A deep model for urban traffic revitalization indexData & Knowledge Engineering, Vol. 135 | 1 Sep 2021 Cross Ref Spectral moments of hypertrees and their applicationsLinear and Multilinear Algebra, Vol. 13 | 15 July 2021 Cross Ref A Harary-Sachs theorem for hypergraphsJournal of Combinatorial Theory, Series B, Vol. 149 | 1 Jul 2021 Cross Ref Binomial incidence matrix of a semigraphDiscrete Mathematics, Algorithms and Applications, Vol. 13, No. 03 | 20 October 2020 Cross Ref The solution of vibroacoustic linear systems as a finite sum of transmission pathsMechanical Systems and Signal Processing, Vol. 153 | 1 May 2021 Cross Ref On the multiple eigenvalue of Randić matrix of treesLinear and Multilinear Algebra, Vol. 69, No. 6 | 2 June 2019 Cross Ref A reduction formula for the characteristic polynomial of hypergraph with pendant edgesLinear Algebra and its Applications, Vol. 611 | 1 Feb 2021 Cross Ref Using Machine Learning to Quantify the Robustness of Network ControllabilityMachine Learning for Networking | 3 March 2021 Cross Ref Autocatalytic Networks: An Intimate Relation between Network Topology and DynamicsBadal Joshi and Gheorghe CraciunSIAM Journal on Applied Mathematics, Vol. 81, No. 4 | 10 August 2021AbstractPDF (521 KB)Parameterized complexity of determinant and permanentTheoretical Computer Science, Vol. 845 | 1 Dec 2020 Cross Ref Inverses of non-bipartite unicyclic graphs with a unique perfect matchingLinear and Multilinear Algebra | 6 September 2020 Cross Ref A Unified View on Bipartite Species-reaction Graphs and Their Relation to Interaction Graphs and Qualitative Dynamics of Chemical Reaction NetworksElectronic Notes in Theoretical Computer Science, Vol. 350 | 1 Sep 2020 Cross Ref Laplacian matching polynomial of graphsJournal of Algebraic Combinatorics, Vol. 52, No. 1 | 6 June 2019 Cross Ref Advances and challenges in single-molecule electron transportReviews of Modern Physics, Vol. 92, No. 3 | 17 July 2020 Cross Ref Stably computing the multiplicity of known roots given leading coefficientsNumerical Linear Algebra with Applications, Vol. 27, No. 2 | 4 December 2019 Cross Ref On the spectral properties of Feigenbaum graphsJournal of Physics A: Mathematical and Theoretical, Vol. 53, No. 2 | 19 December 2019 Cross Ref Minimal Sufficient Conditions for Structural Observability/Controllability of Composite Networks via Kronecker ProductIEEE Transactions on Signal and Information Processing over Networks, Vol. 6 | 1 Jan 2020 Cross Ref Input-Output Networks, Singularity Theory, and HomeostasisAdvances in Dynamics, Optimization and Computation | 21 July 2020 Cross Ref Automatic generation of fabrication drawings for façade mullions and transoms through BIM modelsAdvanced Engineering Informatics, Vol. 42 | 1 Oct 2019 Cross Ref Spectrally arbitrary patterns over rings with unityLinear Algebra and its Applications, Vol. 576 | 1 Sep 2019 Cross Ref Neural Task Planning With AND–OR Graph RepresentationsIEEE Transactions on Multimedia, Vol. 21, No. 4 | 1 Apr 2019 Cross Ref Computation of maximum likelihood estimates in cyclic structural equation modelsThe Annals of Statistics, Vol. 47, No. 2 | 1 Apr 2019 Cross Ref Organizing Project Actors for Collective Decision-Making about Interdependent RisksComplexity, Vol. 2019 | 20 Mar 2019 Cross Ref Inverses of Bipartite GraphsCombinatorica, Vol. 38, No. 5 | 13 June 2017 Cross Ref Key Features of Turing Systems are Determined Purely by Network TopologyPhysical Review X, Vol. 8, No. 2 | 20 June 2018 Cross Ref Physarum-Inspired Solutions to Network Optimization ProblemsShortest Path Solvers. From Software to Wetware | 27 April 2018 Cross Ref Algorithms and Training for Weighted Multiset Automata and Regular ExpressionsImplementation and Application of Automata | 29 June 2018 Cross Ref An Introduction to the Network Weight MatrixGeographical Analysis, Vol. 50, No. 1 | 5 July 2017 Cross Ref Sensor selection cost optimisation for tracking structurally cyclic systems: a P-order solutionInternational Journal of Systems Science, Vol. 48, No. 11 | 22 May 2017 Cross Ref Simulating Chemical Kinetics Without Differential Equations: A Quantitative Theory Based on Chemical PathwaysThe Journal of Physical Chemistry Letters, Vol. 8, No. 16 | 3 August 2017 Cross Ref Characterization of poplar metabotypes via mass difference enrichment analysisPlant, Cell & Environment, Vol. 40, No. 7 | 6 April 2017 Cross Ref On characteristic and permanent polynomials of a matrixSpecial Matrices, Vol. 5, No. 1 | 26 Jan 2017 Cross Ref The determinant of an antiadjacency matrix of a directed cycle graph with chords1 Jan 2017 Cross Ref Determinant of antiadjacency matrix of union and join operation from two disjoint of several classes of graphs1 Jan 2017 Cross Ref Graph invertibility and median eigenvaluesLinear Algebra and its Applications, Vol. 513 | 1 Jan 2017 Cross Ref Relations Between Connected and Self-Avoiding Hikes in Labelled Complete DigraphsGraphs and Combinatorics, Vol. 32, No. 5 | 2 April 2016 Cross Ref Simulation analysis on urban traffic congestion propagation based on complex network2016 IEEE International Conference on Service Operations and Logistics, and Informatics (SOLI) | 1 Jul 2016 Cross Ref Changing Project Structure to Mitigate Its ComplexityManaging Complex, High Risk Projects | 19 December 2015 Cross Ref Mathematical Aspects of Omega PolynomialDistance, Symmetry, and Topology in Carbon Nanomaterials | 17 August 2016 Cross Ref Indexing Simple Graphs by Means of the Resistance DistanceIEEE Access, Vol. 4 | 1 Jan 2016 Cross Ref Moore Graphs and Cycles Are Extremal Graphs for Convex CyclesJournal of Graph Theory, Vol. 80, No. 1 | 12 November 2014 Cross Ref Polymers, Nonlinearity inEncyclopedia of Complexity and Systems Science | 23 September 2015 Cross Ref Odd 2-factored snarksEuropean Journal of Combinatorics, Vol. 36 | 1 Feb 2014 Cross Ref On Randić energyLinear Algebra and its Applications, Vol. 442 | 1 Feb 2014 Cross Ref Graphs and MatricesMathematical Tools for Data Mining | 27 March 2014 Cross Ref A formula for all minors of the adjacency matrix and an applicationSpecial Matrices, Vol. 2, No. 1 | 12 February 2014 Cross Ref Digraphs and MatricesHandbook of Linear Algebra, Second Edition | 26 November 2013 Cross Ref Topology design in networked estimation: A generic approach2013 American Control Conference | 1 Jun 2013 Cross Ref Are Stacker Crane Problems easy? A statistical studyComputers & Operations Research, Vol. 40, No. 3 | 1 Mar 2013 Cross Ref The fundamental chemical equation of aromaticityPhysical Chemistry Chemical Physics, Vol. 15, No. 11 | 1 Jan 2013 Cross Ref A graph spectrum framework for optimizing the combination process of geometric biclustering2012 IEEE International Conference on Systems, Man, and Cybernetics (SMC) | 1 Oct 2012 Cross Ref Basic Reproduction Ratio for a Fishery Model in a Patchy EnvironmentActa Biotheoretica, Vol. 60, No. 1-2 | 15 March 2012 Cross Ref Graph-Theoretical Descriptors for Branched PolymersStatistical Modelling of Molecular Descriptors in QSAR/QSPR | 9 March 2012 Cross Ref Balance in gain graphs – A spectral analysisLinear Algebra and its Applications, Vol. 436, No. 5 | 1 Mar 2012 Cross Ref A new expression for matching polynomialsDiscrete Mathematics, Vol. 312, No. 4 | 1 Feb 2012 Cross Ref Basic ResultsA Textbook of Graph Theory | 9 August 2012 Cross Ref Domination in GraphsA Textbook of Graph Theory | 9 August 2012 Cross Ref Spectral Properties of GraphsA Textbook of Graph Theory | 9 August 2012 Cross Ref Directed GraphsA Textbook of Graph Theory | 9 August 2012 Cross Ref ConnectivityA Textbook of Graph Theory | 9 August 2012 Cross Ref TreesA Textbook of Graph Theory | 9 August 2012 Cross Ref Independent Sets and MatchingsA Textbook of Graph Theory | 9 August 2012 Cross Ref Eulerian and Hamiltonian GraphsA Textbook of Graph Theory | 9 August 2012 Cross Ref Graph ColoringsA Textbook of Graph Theory | 9 August 2012 Cross Ref PlanarityA Textbook of Graph Theory | 9 August 2012 Cross Ref Triangulated GraphsA Textbook of Graph Theory | 9 August 2012 Cross Ref Communication strategies to ensure generic networked observability in multi-agent systems2011 Conference Record of the Forty Fifth Asilomar Conference on Signals, Systems and Computers (ASILOMAR) | 1 Nov 2011 Cross Ref Matrices of a GraphGraphs: Theory and Algorithms | 22 February 2011 Cross Ref Graph Polynomials and Their Applications II: Interrelations and InterpretationsStructural Analysis of Complex Networks | 16 September 2010 Cross Ref Some Reflections on Discrete Mathematical Models in Behavioral, Cognitive and Social SciencesProof, Computation and Agency | 10 March 2011 Cross Ref On the Structural Non-identifiability of Flexible Branched PolymersEntropy, Vol. 11, No. 4 | 20 November 2009 Cross Ref A graph-theoretic method for the basic reproduction number in continuous time epidemiological modelsJournal of Mathematical Biology, Vol. 59, No. 4 | 2 December 2008 Cross Ref SPECTRUM BASED TECHNIQUES FOR GRAPH ISOMORPHISMInternational Journal of Foundations of Computer Science, Vol. 20, No. 03 | 30 April 2012 Cross Ref Polymers, Non-linearity inEncyclopedia of Complexity and Systems Science | 1 Jan 2009 Cross Ref On the multiplicities of eigenvalues of a Hermitian matrix whose graph is a treeAnnali di Matematica Pura ed Applicata, Vol. 187, No. 2 | 27 October 2007 Cross Ref The coefficients of the Ihara zeta functionInvolve, a Journal of Mathematics, Vol. 1, No. 2 | 1 July 2008 Cross Ref On a conjecture about the μ-permanentLinear and Multilinear Algebra, Vol. 53, No. 3 | 1 Jun 2005 Cross Ref Interlacing Properties for Hermitian Matrices Whose Graph is a Given TreeC. M. da FonsecaSIAM Journal on Matrix Analysis and Applications, Vol. 27, No. 1 | 31 July 2006AbstractPDF (145 KB)Isospectral polygons, planar graphs and heat contentProceedings of the American Mathematical Society, Vol. 131, No. 11 | 18 June 2003 Cross Ref Graph-Theoretical Method for Rouse-Ham Dynamics.Nihon Reoroji Gakkaishi, Vol. 30, No. 1 | 1 Jan 2002 Cross Ref Rectifying a misbelief: Frank Harary's role in the discovery of the coefficient-theorem in chemical graph theoryJournal of Mathematical Chemistry, Vol. 16, No. 1 | 1 Jan 1994 Cross Ref Some determinant expansions and the matrix-tree theoremDiscrete Mathematics, Vol. 124, No. 1-3 | 1 Jan 1994 Cross Ref LDLT factorizations of adjacency matrices where D is block diagonalLinear Algebra and its Applications, Vol. 162-164 | 1 Feb 1992 Cross Ref Integer LU-factorizationsLinear Algebra and its Applications, Vol. 150 | 1 May 1991 Cross Ref Matrices, Digraphs, and DeterminantsJohn S. Maybee, D. D. Olesky, Driessche P. van den, and G. WienerSIAM Journal on Matrix Analysis and Applications, Vol. 10, No. 4 | 17 July 2006AbstractPDF (2263 KB)The Pólya Picture Album—Encounters of a Mathematician . Edited by Gerald L. AlexandersonThe American Mathematical Monthly, Vol. 96, No. 8 | 2 February 2018 Cross Ref Isospectbal graphs revisitedJournal of Molecular Structure: THEOCHEM, Vol. 185 | 1 Mar 1989 Cross Ref Perfect graphs and complex surface singularities with perfect local fundamental groupTohoku Mathematical Journal, Vol. 41, No. 4 | 1 Jan 1989 Cross Ref The challenge of characterizing branching in molecular speciesDiscrete Applied Mathematics, Vol. 19, No. 1-3 | 1 Mar 1988 Cross Ref On graphs with signed inversesNetworks, Vol. 18, No. 3 | 1 Jan 1988 Cross Ref On the Characteristic Equations of the Characteristic PolynomialMilan RandićSIAM Journal on Algebraic Discrete Methods, Vol. 6, No. 1 | 17 July 2006AbstractPDF (1995 KB)IntroductionGraphs and Order | 1 Jan 1985 Cross Ref A novel approach to the characterization of chemical structuresInternational Journal of Quantum Chemistry, Vol. 26, No. S18 | 1 Mar 1984 Cross Ref Counting the spanning trees of a labelled molecular-graphMolecular Physics, Vol. 50, No. 4 | 23 August 2006 Cross Ref Tree counting polynomials for labelled graphs part I: PropertiesJournal of the Franklin Institute, Vol. 312, No. 6 | 1 Dec 1981 Cross Ref Permanental polynomials of graphsLinear Algebra and its Applications, Vol. 38 | 1 Jun 1981 Cross Ref Partition technique and molecular graph theoryInternational Journal of Quantum Chemistry, Vol. 20, No. S15 | 19 June 2009 Cross Ref A graph theoretical recurrence formula for computing the characteristic polynomial of a matrixCombinatorics and Graph Theory | 9 October 2006 Cross Ref Calculation of the determinant of the adjacency matrix and the stability of conjugated moleculesInternational Journal of Quantum Chemistry, Vol. 18, No. 1 | 1 Jul 1980 Cross Ref Algorithms for finding directed graph isomorphisms by finite automataInternational Journal of Computer & Information Sciences, Vol. 9, No. 2 | 1 Apr 1980 Cross Ref Chemical graph theory. II. On the graph theoretical polynomials of conjugated structuresInternational Journal of Quantum Chemistry, Vol. 18, No. S14 | 19 June 2009 Cross Ref The graph theoretical formulas for determinant expansionsInternational Journal of Quantum Chemistry, Vol. 18, No. S14 | 19 June 2009 Cross Ref Random walks and their diagnostic value for characterization of atomic environmentJournal of Computational Chemistry, Vol. 1, No. 4 | 1 Jan 1980 Cross Ref Spectral criterion for cycle balance in networksJournal of Graph Theory, Vol. 4, No. 1 | 1 Jan 1980 Cross Ref Matrix measures for transitivity and balance*The Journal of Mathematical Sociology, Vol. 6, No. 2 | 26 August 2010 Cross Ref Automorphism group and category of cospectral graphsActa Mathematica Academiae Scientiarum Hungaricae, Vol. 31, No. 3-4 | 1 Sep 1978 Cross Ref The decomposition of systems of procedures and algebraic equationsNumerical Analysis | 27 August 2006 Cross Ref Comment on a graph-theoretical description of heteroconjugated moleculesChemical Physics Letters, Vol. 51, No. 1 | 1 Oct 1977 Cross Ref A survey of sparse matrix researchProceedings of the IEEE, Vol. 65, No. 4 | 1 Apr 1977 Cross Ref A Fast Backtracking Algorithm to Test Directed Graphs for Isomorphism Using Distance MatricesJournal of the ACM, Vol. 23, No. 3 | 1 Jul 1976 Cross Ref Graphical studies on the relations between the structure and reactivity of conjugated systems: the role of non-bonding molecular orbitalsJournal of Molecular Structure, Vol. 28, No. 2 | 1 Oct 1975 Cross Ref On resonance theoryChemical Physics Letters, Vol. 34, No. 2 | 1 Jul 1975 Cross Ref Isospectral graphs and moleculesTetrahedron, Vol. 31, No. 2 | 1 Jan 1975 Cross Ref Computing the Characteristic polynomial of a graphGraphs and Combinatorics | 26 August 2006 Cross Ref Isospectral moleculesTetrahedron Letters, Vol. 15, No. 8 | 1 Jan 1974 Cross Ref On the number of nonzeros added when Gaussian elimination is performed on sparse random matricesMathematics of Computation, Vol. 28, No. 125 | 1 January 1974 Cross Ref The characteristic polynomial of a graphJournal of Combinatorial Theory, Series B, Vol. 12, No. 2 | 1 Apr 1972 Cross Ref A graph polynomial and its applicationsDiscrete Mathematics, Vol. 3, No. 4 | 1 Jan 1972 Cross Ref ALGEBRAIC ISOMORPHISM INVARIANTS FOR GRAPHS OF AUTOMATA††This work was supported by the U.S. Air Force, Rome Air Development Center under Contract AF30 (602)-3546. It is derived from a disertation submitted in partial fulfillment of the requirements for the degree of Doctor of Philosophy at The University of Michigan.Graph Theory and Computing | 1 Jan 1972 Cross Ref BibliographyApplied Graph Theory | 1 Jan 1971 Cross Ref Graph theory and molecular orbitalsNew Concepts II Cross Ref Determinants, Permanents and Bipartite GraphsMathematics Magazine, Vol. 42, No. 3 | 16 February 2018 Cross Ref Generalized Matrix Functions and the Graph Isomorphism ProblemJames TurnerSIAM Journal on Applied Mathematics, Vol. 16, No. 3 | 12 July 2006AbstractPDF (629 KB)On Directed Graph Solutions of Linear Algebraic EquationsWai-Kai ChenSIAM Review, Vol. 9, No. 4 | 18 July 2006AbstractPDF (1718 KB)Graphs and MatricesFrank HararySIAM Review, Vol. 9, No. 1 | 18 July 2006AbstractPDF (820 KB)Drum Shapes and Isospectral GraphsJournal of Mathematical Physics, Vol. 7, No. 12 | 1 Dec 1966 Cross Ref Self-Avoiding Paths and the Adjacency Matrix of a GraphJ. PonsteinSIAM Journal on Applied Mathematics, Vol. 14, No. 3 | 28 July 2006AbstractPDF (996 KB) Volume 4, Issue 3| 1962SIAM Review197-296 History Submitted:21 July 1961Published online:01 August 2006 InformationCopyright © 1962 © Society for Industrial and Applied MathematicsPDF Download Article & Publication DataArticle DOI:10.1137/1004057Article page range:pp. 202-210ISSN (print):0036-1445ISSN (online):1095-7200Publisher:Society for Industrial and Applied Mathematics