6
votes
Accepted
Quotient graph of a tree
Yes, if $G$ is connected (and non-empty for simplicity).
Choose a vertex $v\in V(G)$. We define a tree $T$ in which the vertices are all the paths in $G$ that start in $v$ (including the path of ...
- 13.6k
5
votes
Accepted
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
The answer to this question is No.
Let us assume $V = \{1,2,3,4,5,6\}$ and consider degree sequences $a = [3,2,2,1,0,0]$, $b = [1,0,0,3,2,2]$ and $c = a+b = [4,2,2,4,2,2]$.
The only simple graph with ...
- 1,444
3
votes
Number of occurrences of subgraphs as a unique identifier
If you can answer this question, and prove it, you'll be famous. It is the reconstruction problem that has been open since 1957.
Basically, except for the trivial case $n=2$, nobody can prove that ...
- 37.7k
2
votes
Simple graphs with prescribed degrees as disjoint union of simple subgraphs with prescribed degrees
I think your property is true and can be shown recursively depending on the size $n$ of the graph.
Existence
For $n=2$ well one of the sequences has to be (0,0), so the other one is equal to $c$: it ...
- 21
2
votes
Counting number of special subset of vertices in a tree
Let us prove the desired bound $2(n-3)^2$ for the number of unordered odd pairs by induction on $n$, base case being $n=4$.
Suppose that $n\geq 5$. Take a leaf $a$ with a unique neighbour $b$; let $\...
- 23.7k
1
vote
Some questions about induced subgraphs of the directed hypercube graph
I thought this would be a full solution (i.e. showing (1) is $\sqrt{n}/2$), but in fact it only yields (1) is less than or equal to $\sqrt{n}/\sqrt{2}$. I'll still post it after all of the effort, ...
- 2,621
1
vote
About a generalization of complete graphs
I've found this in the literature: "The k-truss of G is the largest subgraph of G in which every edge is contained in at least (k-2) triangles within the subgraph.". See:
https://arxiv.org/...
- 111
Only top scored, non community-wiki answers of a minimum length are eligible