All Questions
31 questions
1
vote
0
answers
134
views
Number of ways to place 4 kings on nxn chessboard
I have a $n\times n$ chessboard and 4 kings inside it. My goal is to count the number of arrangements where some of them are non-attacking or mutually attacking, for example:
In the case where the $4$...
- 47
3
votes
2
answers
197
views
Proper Latin sub-squares of generalized Latin squares
Say we have a generalization of a Latin square, where the square is of size $n \times n$, $n = ab$ and each row and each column has $b$ occurrences of each of $[1, \dots, a]$. Is there always ...
- 31
0
votes
0
answers
37
views
Largest root of the Adjacency matrix of two graphs (comparison)
Let $G$ and $H$ be two graphs whose spectral radius (largest eigenvalue) of the adjacency matrix is the largest root of the following polynomial:
$$P_G(x) = x^6-x^5-(2a-n+5)x^4+(2a-n+1)x^3+2(5a-3n+5)x^...
- 199
2
votes
0
answers
203
views
Permutation similarity of matrices with many distinct entries
This is related to graph isomorphism.
Here matrices are square $n \times n$ with non-negative integer entries.
Two matrices $A,B$ are permutation similar if there exist
permutation matrix $P$ such ...
- 25.4k
6
votes
1
answer
726
views
Combinatorics and symmetry in matrices under row and column swaps
Suppose we have a $m\times n$ matrix and a sequence of numbers with which to fill the matrix, $\{c_1,c_2 \dots c_k \}$. I like to think of the numbers as colors, hence the notation. How many unique ...
3
votes
2
answers
316
views
Relation graph isomorphism to discrete logarithm
$\DeclareMathOperator\ora{ora}$Let $A_0$ be the adjacency matrix of graph $G$ and $P_0$
permutation matrix of multiplicative order $\rho$.
Let $X$ be positive integer and $B_0=P_0^X A_0 P_0^{-X}$.
Q1 ...
- 25.4k
1
vote
1
answer
165
views
Combinatorial graph optimization problem on integer adjacency matrices
We are given a $n\times n$ symmetric matrix $M$ whose entries are positive integers.
Let $z_{i,j}:=\frac{M_{i,j}}{M_{i,j}+\sum_{k\neq i,j}\min(M_{i,k},M_{k,j})}$ for all $1\le i<j \le n$, and
$z:=\...
- 1,677
2
votes
2
answers
330
views
Polynomial time algorithm for rigid graph isomorphism
We found, implemented and tested algorithm
for graph isomorphism and it appears to be polynomial
time if the graph is rigid.
Q1 Is the algorithm below correct and polynomial time for rigid graphs?
A ...
- 25.4k
34
votes
1
answer
789
views
Which graphs on $n$ vertices have the largest determinant?
This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.
The determinant of ...
- 12.7k
4
votes
2
answers
600
views
Co-trees of a simple graph
Consider fundamental cycles (say $k$ of them) of a specific spanning tree of a simple graph (with $m$ edges) which is also connected and has no one-edge bonds.
Make the graph directed (in an arbitrary ...
- 419
2
votes
0
answers
119
views
Complete graph invariant based on integer programming?
Roughly speaking, we are trying to find complete graph invariant
as the lexicographically first matrix from the permutations
of the adjacency matrix.
Let $G$ be graph, possibly directed graph, of ...
- 25.4k
2
votes
0
answers
154
views
What characterizes the incidence matrix of a tripartite hypergraph?
The incidence matrix of a graph $G = (V,E)$ is a matrix with $|V|$ rows and $|E|$ columns, in which element $v,e$ is $1$ if node $v$ is incident to edge $e$, and $0$ otherwise.
In bipartite graphs, ...
- 3,549
1
vote
1
answer
847
views
Do there exist graphs whose adjacency matrix is positive semi-definite? [closed]
If so, could you provide examples and specify the conditions under which this occurs? Thank you in advance
4
votes
1
answer
140
views
Counting adjacency matrices
Here is a question that has come up in the context of a problem that involves counting partially ordered sets.
For an adjacency matrix $A$, let $p$ be the sum of elements in the strict upper ...
- 192
7
votes
0
answers
177
views
Matrix of high rank mod $2$: must it have a large non-singular minor (with disjoint rows and columns)?
Let $A$ be a $2n$-by-$2n$ matrix with entries in
$\mathbb{Z}/2\mathbb{Z}$ such that, for every $2n$-by-$2n$ diagonal
matrix $D$ with entries in $\mathbb{Z}/2\mathbb{Z}$, the matrix $A+D$
has rank $\...
- 20.2k
1
vote
1
answer
60
views
Rank and edges in a combinatorial graph?
Fix a $d\in\mathbb N$ and consider the matrix $M\in\{0,1\}^{2^d\times d}$ of all $0/1$ vectors of length $d$. Consider the matrix $G\in\{0,1\}^{n\times n}$ whose $ij$ the entry is $0$ if inner product ...
- 13.9k
11
votes
1
answer
467
views
Correspondence between matrix multiplication and a graph operation of Lovász
In his book "Large networks and graph limits", Lovász describes a multiplication operation (he calls it concatenation) on "bi-labeled graphs". An $(m,n)$ bi-labeled graph is a ...
- 2,339
2
votes
2
answers
234
views
Adjacency matrix of total graph
Is there a nice way of relating the adjacency, incidence , Laplacian matrices and other matrices associated to a graph of a total graph with its original graph, or, say, at least relating that of the ...
- 2,089
0
votes
1
answer
125
views
Estimating Maximal-Clique of Metric Graphs via the Rank of their Adjacency Matrix
Let $\mathrm{M}\in\lbrace0,1\rbrace^n$ be the adjacency matrix of a graph $\mathrm{G}\left(V,E\subseteq\lbrace\lbrace u,v\rbrace| u,v\in V\rbrace\right)$ of order $n$.
Let $\mathrm{G}$ ...
- 13.2k
28
votes
3
answers
2k
views
Is every positive integer the permanent of some 0-1 matrix?
In the course of discussing another MO question we realized that we did not know the answer to a more basic question, namely:
Is it true that for every positive integer $k$ there exists a balanced ...
- 82.6k
2
votes
0
answers
956
views
The (minimum) rank of a relation
$\DeclareMathOperator{\rk}{rk}$
For an integer $n\ge 1$, let $\mathcal R_n$ denote the set of all reflexive binary relations on $[n]$. I define the rank of a relation $R\in\mathcal R_n$ to be the ...
- 23k
1
vote
1
answer
647
views
If the two smallest eigenvalues of the Laplacian matrix of a network are equal to zero, then does it mean that the network is not connected? [closed]
What does it mean if the two smallest eigenvalues of the Laplacian matrix of a graph are equal to zero?
- 13
2
votes
1
answer
449
views
Extracting a full rank matrix from a 0-1 matrix
If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of ...
- 23
1
vote
0
answers
455
views
Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition
Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...
- 267
1
vote
0
answers
204
views
Complexity of reordering a matrix which consists independent sub matrices
Introduction:
Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$.
$A_x$ is the symmetric matrix of the graph $(G-x)$, ...
- 267
2
votes
1
answer
156
views
Are there non-isomorphic graphs with rationally orthogonal similar adjacency matrices?
Let $A_G,A_H$ be the adjacency matrices of two non-isomorphic graphs.
Let $P$ be orthogonal matrix with rational entries.
Is it possible $A_G = P^{-1}A_H P$?
Paper
gives algorithm for recognizing ...
- 25.4k
10
votes
2
answers
2k
views
When are the adjacency matrices of non-isomorphic graphs similar?
From Wikipedia.
In linear algebra, two n-by-n matrices A and B are called similar if
$$ B = P^{-1} A P$$
for some invertible n-by-n matrix $P$.
If $P$ is a permutation matrix, $A$ and $B$ are ...
- 25.4k
0
votes
0
answers
244
views
Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$
Valiant
shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$
to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$
for certain efficiently computable $t(F)$ and matrix $...
- 25.4k
4
votes
0
answers
657
views
determinant of fibonacci-sum graphs
We have a simple graph with vertices $\{v_1, v_2, ... v_n\}$.
The adjacency matrix of this graph is $A= (a_{ij})$ so that
$a_{ij}=1$ if $i+j$ belongs to the Fibonacci sequence;
$a_{ij}=0$ ...
- 41
4
votes
0
answers
434
views
Smallest matrix covered by many random n by n matrices
We say that a matrix $M$ can be covered by a (smaller) matrix $N$ if every entry in $M$ is contained in some submatrix of $M$ that exactly equals to $N$, up to reordering the rows and columns of $N$. ...
- 51
4
votes
0
answers
351
views
Combinatorics of signed oriented graphs/skew-symmetric matrices
Consider a "complete" signed graph on $n$ vertices indexed by
$1,2,\dots,n$, that is, a graph in which any two distinct vertices $i$ and $j$ are connected by an oriented edge.
For each pair of ...
- 13.5k