# Tagged Questions

Studying graphs using algebra (for example, linear algebra and abstract algebra) as a tool.

28 views

### Maximize the number of non zero elements of a product of binary matrices.

I want to find two binary matrices $A$ of size $N \times M$ and $B$ of size $M \times N$ such that: $AB=C$ is a strictly lower-triangular matrix ($j \geq i \implies C_{ij}=0$) The number of ...
12 views

### For what functions $f$ is $x^{\sf T}Lf(x) \geq 0$?

Let $L = L^{\sf T} \in \mathbb{R}^{n\times n}$ be a (weighted) Laplacian matrix of a connected undirected graph. For those not familiar with Laplacians (they are positive semidefinite); for simplicity ...
18 views

### Surjective homomorphism preserves planarity?

I was just wondering if for surjective homomorphism of G to H, where G is planar hold that H is planar as well. This is clearly false for non-surjective ones, but for surjective? How it is with ...
36 views

### Any undirected graph on 9 vertices with minimum degree at least 5 contains a subgraph $K_4$?

Let $G$ be simple undirected graph with degree of every vertices is at least 5. Prove or disprove that $G$ contains subgraph $K_4$. I came up with this question when I were trying to find Ramsey ...
54 views

### Non-trivial graph automorphism groups with $D_n$ as subgroup

I understand that the automorphism group of an $n$ cycle graph is the dihedral group $D_n$ of order $2 n$. From the comment of @Christian, I also understand that $S_n$ is the automorphism group of the ...
72 views

### Does a 2-connected graph, say $G$ have a vertex, say $v$, such that $G-v$ is still 2-connected?

I have been trying to solve this problem for some days. Then, I put the problem here, and it is here for some days. I appreciate it if someone even give me some hint. Assume that $G$ is a 2-...
27 views

### how to find the angle of Lovasz umbrella

in the book Thirty-three Miniatures: Mathematical and Algorithmic Applications of in problem 28 The Secret Agent and the Umbrella page 132 (pdf 140) we want to find an orthogonal reperesentation of ...
24 views

### Isomorphism of two graphs using adjacency matrix

How can I show that the following two graphs are isomorphic: Steps: The given graphs can be written as:
21 views

### Quasi-Group represented by a graph which is not a Triangle-Free Graph locally

Can each of all quasi-groups be represented by a graph (latin square graph), which is not locally triangle free graph ? Quasi Group can be represented by Latin Square matrix, thus by a Latin ...
23 views

44 views

### How to detect automorphism of union of graphs?

On page 1 of Lecture 2, Algebra and Computation , (Course Instructor: V. Arvind), there is a theorem- Theorem 2. With Graph − Iso (graph isomorphism) as an oracle, there is a polynomial time ...
29 views

### How to find the size of the largest connected component of a graph from the adjacency matrix, without using BFS/DFS?

Is there a known way to compute the size of the largest connected component of an undirected graph using just the matrix operations on the adjacency matrix or the laplacian matrix of the graph?
61 views

28 views

40 views

### Merging two nodes in a directed graph with transitions

Let's say I have $M=\begin{bmatrix}1&2&1\\ 4&2&0 \\ 1& 1& 1\end{bmatrix}$, a $3\times3$ matrix which is the transition matrix or adjacency matrix of a $3$-node graph. I would ...
56 views

### How does an automorphism of vertices stabilize edges?

How an automorphism of vertices stabilizes edges ? There are some permutations which acts on vertices and edges at the same time. For example, $\pi=(24)$(an automorphism) permutes or switches ...
50 views

### Subgraph of integral graph is also integral??

Background: An integral graph is a graph whose spectrum consists entirely of integers (see [1]). Example: Complete graph $K_n$, since spectrum$(K_n) = (n-1,-1,\ldots,-1)$ Question Is the induced ...
$X, X'$ be two connected graphs and let $Z$ be there $Disjoint$ union. $D=Aut(X) \times Aut(X')$ . How does $|D|< |Aut(Z)|$ if and only if $X \simeq X'$ ? An example would be helpful. In ...