9
votes

Accepted

### Joining the $2^k$ points of $\{0,1\}^k$ with the shortest tree

I suspect that the optimum, for a cube of side length $2$, is $2^k \sqrt{3} - 2 \sqrt{3}+2$. Note that the optimum if we use edges of the cube is $2 (2^k-1)$, so this is better by a factor of roughly $...

8
votes

Accepted

### *Friendly* coloring of a digraph

Carsten Thomassen (1983) proved that a digraph with minimal out-degree at least 3 has two vertex-disjoint cycles, call them $C_1$, $C_2$ and color black and white respectively. Then proceed as follows:...

8
votes

### Is a finite lattice determined by its Hasse diagram (as a graph)?

This is still far from true. Consider for example these lattices (just a random example):

7
votes

Accepted

### What determines internalization of graph-structures into the set world?

The answer is yes for equinumerosity (provided...), but no for graphs.
Equinumerosity. KM is commonly taken to include the axiom of choice and furthermore the axiom of global choice, and this makes ...

5
votes

Accepted

### If $\widehat{\Gamma}$ is a simply connected clique complex then $\mathrm{Out}(A_\Gamma)$ is an infinite group

What about the following tesselation of the sphere? Am I missing something if I say that there are no disconnecting stars nor two distinct vertices such that the link of one is contained in the star ...

5
votes

Accepted

### Is every connected edge-swapping graph edge-transitive?

No - consider the vertex-and-edge graph of a truncated cube. Some but not all edges are part of 3-cycles, so this graph is not edge-transitive, but it is clearly edge-swapping.

3
votes

### On the relationship between graph isomorphism and equivalence in ETL workflow dependency graphs

We consider two directed acyclic graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ representing task dependency structures. Here, $V = \{v_1, v_2, ..., v_n\}$ is the set of vertices (tasks) identical for ...

3
votes

Accepted

### Generate all non-isomorphic caterpillar trees with $n$ vertices

Here is a SageMath code generating caterpillar graphs on $n$ nodes based on enriching a path graph with leaves. As an example it shows all such graphs on 6 nodes.

3
votes

Accepted

### "Spanning trees" for connected linear hypergraphs

Counterexample. Let $\mathbb N=\{1,2,3,\dots\}$. For $n\in\mathbb N$ let $[n]=\{1,2,\dots,n\}$. Let $V=\mathbb N\times\mathbb N$. For $n\in\mathbb N$ let $e_n=\{n\}\times\mathbb N$ and $f_n=[n]\times\{...

3
votes

Accepted

### Function of eigenvalues of Laplacian matrix

Since the number of edges $e(G)$ equals the trace of Laplacian matrix of $G$ divided by 2, we have
$$f(\mu_1,\mu_2,\dots\mu_n) = \frac{\mu_1+\mu_2+\cdots+\mu_n}2.$$

2
votes

Accepted

### Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs

It is highly unlikely that such a generalization would exist, because the 3-dimensional matching problem is NP-complete, while polynomial identity testing can be solved efficiently using randomized ...

2
votes

Accepted

### The perfect matching problem of planar graph

You don't even need that whole 4-block tree stuff; you can read the result directly by contracting the `rest' into vertices.
More details: As in the above proof, fix a set $T$ that minimizes $odd(T)-|...

1
vote

### How sensitive are Neural Networks to weight change?

Output of the ReLU network is
$$v = \sum_{ij} X_i A_{ij} w^{(1)}_{ij} \cdots w^{(L)}_{ij} $$
where $i$ is the input $j$ is the path and $A_{ij}$ is $1$ if the path is open and $0$ otherwise. Now if ...

1
vote

### Perfect matchings of a regular, uniform, partite hypergraph

For $r = 3$, if we drop the $3$-partite condition, this is RX3C. If we drop $3$-regular, this is 3DM.
3DM is NP-complete, even when the degree is bounded by $3$ (Garey and johnson).
We can get $3$-...

Only top scored, non community-wiki answers of a minimum length are eligible

#### Related Tags

graph-theory × 5222co.combinatorics × 2273

graph-colorings × 530

reference-request × 449

algorithms × 338

pr.probability × 281

spectral-graph-theory × 273

random-graphs × 207

extremal-graph-theory × 205

gr.group-theory × 193

computational-complexity × 191

discrete-geometry × 183

linear-algebra × 174

mg.metric-geometry × 141

combinatorial-optimization × 129

matching-theory × 125

set-theory × 107

trees × 107

infinite-combinatorics × 104

hypergraph × 100

bipartite-graphs × 99

hamiltonian-graphs × 99

matrices × 97

perfect-matchings × 96

algebraic-graph-theory × 91