Determinants of box products of paths

DOI10.1016/J.DISC.2012.01.038zbMATH Open1242.05168arXiv1110.3497OpenAlexW2064360228MaRDI QIDQ418902FDOQ418902

Authors: Daniel Pragel 

Publication date: 30 May 2012

Published in: Discrete Mathematics (Search for Journal in Brave)

Abstract: Suppose that G is the graph obtained by taking the box product of a path of length n and a path of length m. Let M be the adjacency matrix of G. If n=m, H.M. Rara showed in 1996 that det(M)=0. We extend this result to allow n and m to be any positive integers, and show that, if gcd(n+1,m+1)>1, then det(M)=0; otherwise, if gcd(n+1,m+1)=1, then det(M)=(-1)^(nm/2).

Full work available at URL: https://arxiv.org/abs/1110.3497

Recommendations

• Determinants of adjacency matrices of graphs
• Determinant of adjacency matrix of square cycle graph
• Decycling number of the box-cross product of two paths
• scientific article; zbMATH DE number 929718
• Determinant of graphs joined by two edges

zbMATH Keywords

graph theoryadjacency matrixdeterminantCartesian productpathbox product

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Determinants, permanents, traces, other special matrix functions (15A15) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20)

Cites Work

• Path polynomials of a circuit: a constructive approach
• Topics in graph theory. Graphs and their Cartesian product
• Title not available (Why is that?)
• Reduction procedures for calculating the determinant of the adjacency matrix of some graphs and the singularity of square planar grids
• On the location of the eigenvalues of Jacobi matrices
• Path polynomials of a graph

Cited In (7)

• Determinants of grids, tori, cylinders and Möbius ladders
• Some determinants of path generating functions. II
• Domino tilings and determinants
• On characteristic and permanent polynomials of a matrix
• Retracts of box products with odd-angulated factors
• Parameterized complexity of determinant and permanent
• On the determinant of bipartite graphs

This page was built for publication: Determinants of box products of paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q418902)