# Tag Info

### Real-world examples of unweighted directed graphs

It's been recognized that adjacency matrix approaches to forming a spectral graph theory is problematic. It's been rediscovered that Eckmann's Combinatorial Hodge theory removes the problems and gives ...
• 361

### Real-world examples of unweighted directed graphs

Disclaimer: I am not an applied mathematician at all and I found this just via some basic Goolging. But the "Stanford Large Network Dataset Collection" (https://snap.stanford.edu/data/) ...
• 22.8k

• 103k
Accepted

### Topology of directed graph $G$ with non-singular adjacency matrix

There is an edge emanating from any vertex of $G$ because otherwise the corresponding row (or column, according to our convention for forming the adjacency matrix) would be zero. Label the vertices as ...
• 2,722
1 vote

### Can we say a partial order set is 2-dimensional if its comparability graph does not contain an asteroidal triple?

It seems that the answer is negative. A graph $G$ is a co-comparability graph if its complement is a comparability graph. The comparability graphs of posets of dimension 2 are exactly the ...
1 vote

### Complexity of maximum weight-sum matching for cycle graphs

With inspiration from the comments I arrived at the following idea: the maximum weight matching on the cycle is converted to a maximum weight matching on a path that is generated by splitting a vertex,...
• 12.6k
1 vote

### Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

For random graphs, there are algorithms that are efficient on average. See for example A fast algorithm on average for solving the Hamilton Cycle problem by Michael Anastos and the references therein. ...
• 78.3k

### Efficient Hamiltonian cycle algorithms for graph classes

Even though the Hamilton path problem is NP-hard, in practice it is usually easy. An efficient algorithm has been known for 50 years. It is "A Search Procedure for Hamilton Paths and Circuits.&...

### Which are good algorithms for finding Hamiltonian path (not necessarily a circle) up to now?

The most efficient exact algorithm for finding Hamilton paths and circuits is "A Search Procedure for Hamilton Paths and Circuits." J. ACM 21 (Oct. 1974), pp 576-580; DOI: 10.1145/321850....

### Interpreting positive semidefinite matrix as a graph

One characterization of semidefinite positive matrices among symetric matrices is that all their principal minors are positive. The determinant of the adjacency matrix of a graph has a graph-theoritic ...
• 188

### Why do we get a connected 2-regular graph?

The construction makes $U$ the Cayley graph associated to an abelian group $G$ and a pair $\pm g$ of elements of $G$.(*) In such a graph all the components are cycles of the same length, namely the ...
• 77.4k
Accepted

### Chromatic number of the insert-and-shift graph on $S_n$

$\mathbf G_n$ contains the complete graph $K_n$. Consider the set of all permutations where the elements $1,\dots, n-1$ are in the usual order in the sense that $\sigma(1) < \dots < \sigma(n-1)$,...
• 137k

### What is this Ramsey problem?

A good reference is Radziszowski's article Small Ramsey Numbers, which gets updated as new results are proven. In particular, this refers to basically all known Ramsey style results. The ones you're ...
• 29.8k

### A question related to "Locally Sidorenko" type problem

If I understand your question correctly, you are asking if there is a sparse graph counting lemma assuming only that the graphon is within $o(p)$ to the density $p$ in cut norm; the Lovasz result ...
• 109k
Accepted

### Homology of independence complex after removing a vertex

There is a fairly standard splitting technique as suggested in the comment, although not necessarily using $v$. Let $G$ be a graph and $v$ is a simplicial vertex. Let $w$ be any neighbor of $v$. Then ...

### Isometric path cover number of the 2 dimensional grid graph

Assume you have $a$ increasing paths (where both coordinates non-strictly increase) and $b$ decreasing ones. We may assume that all of them start and finish at the vertices of the square. Now perform ...
• 22.2k
Already in the plane there are arrangements such that the longest path in their dual covers roughly at most $2/3$ of the regions, therefore they are not Hamiltonian. The reason is that the dual graph ...