Questions tagged [graph-theory]
Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, topological-graph-theory, random-graphs, graph-colorings and several others.
5,164
questions
4
votes
2
answers
893
views
Proving associativity relations by using a group acting on a set of trees?
I was wondering what kind of tools are available (if any) for avoiding pages of bracket manipulations in proving associativity properties.
To be concrete, a (more easily stated) analogue of the ...
- 1,347
4
votes
6
answers
743
views
Reconstructing an ordering of a multiset from its consecutive submultisets
We have a multiset $S$ of size $t$ with $r$ distinct elements, where $t$ is much larger than $r$. We want to reconstruct an ordering $s_1, s_2, ... s_t$ of the elements of $S$ given the values of $t$ ...
- 599
4
votes
2
answers
197
views
Hamilton cycles in $\{0,1\}^n$ with fixed Hamming distance
Let $n>1$ be an integer. For $a,b\in \{0,1\}^n$ let $d_h(a, b)$ denote the Hamming distance of $a$ and $b$. For $k\in \{1,\ldots,n-1\}$ let $H(n,k)$ be the graph on $\{0,1\}^n$ given by the edge ...
- 45.4k
4
votes
1
answer
712
views
Graph isomorphism by invariants
Graph isomorphism is known to be a difficult computational problem. The problem get even worst if we want to find non-isomorphic graphs in a large family of graphs.
Let us call a (numerical) ...
- 1,651
4
votes
1
answer
160
views
Increasing the chromatic number by "folding" two vertices of distance 2
Is there a finite, connected, simple, undirected graph $G=(V,E)$ such that
$G$ is not complete, and
whenever two vertices of distance $2$ are identified ("folded"), then the chromatic number ...
- 45.4k
4
votes
2
answers
477
views
How do eigenvalues of combinatorial Laplacian relates to automorphisms in graphs?
Is there a relation between eigenvalues of the graph Laplacian and the automorphism group of a simple graph?
How are the multiplicities of Laplacian eigenvalues related to the order of the ...
- 171
4
votes
2
answers
409
views
Conditional probability that a random spanning tree contains the edge e
Let $G$ be a connected simple graph with two distinct edges $e,f \in E(G)$. Choose a random spanning tree $T\subseteq G$, my question is whether there are any known upper bound for the following
\...
- 43
4
votes
3
answers
341
views
reference request: voltage in a resistor network is a unique harmonic function
An undirected graph may be regarded as a resistor network where each edge corresponds to a resistor of unit resistance. This paper covers such an approach.
On electric resistances for distance-...
- 419
4
votes
2
answers
2k
views
Connectivity of weighted graph and zero Laplacian eigenvalues
Given an undirected graph $G$, and let $V$ denote its set of vertices and $E$ its set of edges. Suppose that there are no edges connecting the same vertex, and no more than one edge connecting any ...
- 333
4
votes
2
answers
490
views
Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?
Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...
- 221
4
votes
2
answers
717
views
Minimum number of transitive paths in tournament
Let $T$ be a tournament with $n$ vertices (i.e., between every pair of vertices there exists an edge in exactly one direction.) For any $k$, the vertices $A_1,A_2,...,A_k$ form a transitive path if ...
- 175
4
votes
2
answers
218
views
Is the domination number of a combinatorial design determined by the design parameters?
Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$.
Is $\gamma(L(D))$ determined only by $v,k$, ...
- 6,872
4
votes
2
answers
624
views
What is the state of the art on triangle-free strongly regular graphs?
From what I've read I've gathered the following facts:
There are seven known such graphs.
Certain parameter sets are ruled out by the Krein conditions and the absolute bound.
Beyond that, little or ...
- 6,872
4
votes
3
answers
2k
views
Lower bound for sum of square root of the degrees of a connected graph
Consider a finite connected graph.
By Cauchy-Schwarz and the handshake lemma, it is easy to see that $\left( \sum_{i=1}^n \sqrt{d_i} \right)^2 \leq n \sum_{i=1}^n d_i =2mn$, with equality iff the ...
- 311
4
votes
2
answers
911
views
Is there any nontrivial monad on the category of graphs?
The question is in the title, but let me specify what I mean by the category of graphs.
In the context of this question, the category of graphs is the category of symmetric irreflexive relations. ...
- 827
4
votes
3
answers
238
views
Almost all graphs have a subgraph from a large class of graphs with constant order
I will pose the question in relation to trees but the more general question that can be deduced from the title of this post is also very interesting.
I suspect the question might have a very trivial ...
- 3,433
4
votes
3
answers
573
views
Why is this bipartite graph a partial cube, if it is?
Since the set $\{\log(p) \mid p \text{ is prime, } p \le n \}$ for a natural number $n$ is $\mathbb{Q}$-linear independent and since:
$$\log(m) = \sum_{p\mid m} v_p(m) \log(p)$$
we can view each $\log(...
- 2,462
4
votes
1
answer
379
views
Strongly connected components as adjoint functor?
Fix a faithful functor $\Gamma: \mathsf C\longrightarrow \mathsf{Set}$ and think of it as the "underlying points". When it exists, a left adjoint $\mathrm{disc}\dashv \Gamma$ can be thought ...
- 10.3k
4
votes
2
answers
289
views
Can every involution of a symmetric directed graph be written as a power of another symmetry?
Let $D=(V,A)$ be a finite directed graph, and suppose that
$D$ is vertex-transitive,
$D$ is edge-transitive, and
between any two vertices there is at most one edge, in particular, if $(v,w)\in A$ ...
- 12.6k
4
votes
1
answer
199
views
Embedding any graph in a regular graph with the same chromatic number
If $G=(V,E)$ is a simple, undirected graph, is there a regular graph $G_R$ such that $G$ is isomorphic to an induced subgraph of $G_R$ and $\chi(G) = \chi(G_R)$?
- 45.4k
4
votes
2
answers
230
views
Number of non-equivalent graph embeddings
Given a graph $G$, there is a minimal integer $g$ associated with it which captures the minimum genus a surface needs to have so that $G$ embeds in the surface without edge crossings.
Is there a way ...
- 13.7k
4
votes
2
answers
336
views
Can we find 3 disjoint directed Hamiltonian cycles in the cube?
Let $D$ be the digraph on $2^d$ vertices with $d2^d$ edges that we obtain by directing each edge of the $d$-dimensional hypercube in both directions.
Can we partition the edges of $D$ into $d$ ...
- 18.4k
4
votes
2
answers
810
views
Automorphism group of directed complete graph
Given a directed complete graph on $n$ vertices, is there an efficient algorithm for computing its automorphism group? Is there a nontrivial upper bound on the order of its automorphism group? How ...
- 533
4
votes
1
answer
1k
views
Polygamous stable marriage/ assignment problem
I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
- 201
4
votes
1
answer
521
views
Rigid Strongly Regular Graphs
I need a few examples of graphs that are strongly regular as well as rigid, i.e., have only the trivial automorphism. Any references to relevant literature would be appreciated. Thanks.
- 505
4
votes
1
answer
226
views
Divisibility Relation for Spanning Trees of a Graph
Let $A = \big[{1\ 1\atop 1\ 0}\big]$, and let $G_n$ be the graph whose adjacency matrix is
$A^{\otimes n}$. Also let $\kappa(G)$ denote the number of spanning trees of $G$. From a significant amount ...
- 43
4
votes
1
answer
925
views
Coloring tensor products of graphs
Let $ G,H $ are simple finite graphs and $A = G \times H$. Here $ G \times H $ is the tensor product (also called the direct or categorical product) of $ G $ and $ H $.
Let $G$ has smaller chromatic ...
- 24.2k
4
votes
2
answers
1k
views
when does a regular graph have a 1-factorization?
Is there a sufficient condition for a regular graph to have a 1-factorization (i.e. being able to pack all of its edges into disjoint perfect matchings, and excluding one vertex if the number of ...
- 81
4
votes
3
answers
404
views
Name of an operation on graphs
I asked this a week ago on math.SE, but haven't obtained an answer yet, so I hope it is fine to ask this here too.
Let $G$ and $H$ be two possibly directed, non necessarily simple, vertex-labelled ...
- 1,154
4
votes
3
answers
392
views
Finding a subgraph with slightly large size in planar graphs
This question is related to the previous discussion here.
Due to the result of Noga Alon et al., there is an $O((2k)^kn)$ algorithm for deciding whether a planar graph $G$ contains a fixed subgraph $...
- 1,250
4
votes
1
answer
221
views
A distinguishing node property in trees?
Consider a tree with k nodes and for each node v the vector lv = (lv0, lv1, ..., lvk-1) with lvd the number of leaves (!) with distance d to v. I wonder whether two nodes v, w with lv = lw are ...
- 9,628
4
votes
2
answers
502
views
Counting distinct undirected, partially labelled graphs
Suppose I have a hexagonal tile. Each edge can be connected to any subset of the other edges (including none). Connections are undirected, so a->b implies b->a, but they're not necessarily transitive -...
- 203
4
votes
3
answers
417
views
A name for a claw-graph with paths attached to it
I wanted to know if the following family of graphs has a name in graph theory: A claw with paths of any length attached to the three free vertices of the claw. More formally, a connected acyclic ...
- 2,386
4
votes
1
answer
194
views
Harmonic functions as limits of harmonic functions on graphs?
I have recently learned about Rodin and Sullivan's work that proved a conjecture of Thurston involving giving a construction for the map in the Riemann mapping theorem using circle packings and this ...
- 1,065
4
votes
3
answers
718
views
Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?
I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
- 43
4
votes
1
answer
86
views
From equivalent graphs to isomorphic one- Reconstruction Conjecture
Suppose we are working with connected simple graphs.
We say the graph $G$ and $H$ are equivalent if for any spanning tree $T_G$ in $G$ there is an spanning tree $T_H$ in $H$ such that $T_G$ is ...
- 4,748
4
votes
2
answers
209
views
Graphs on $\{0,1\}^n$ based on fixed Hamming distance
Let $n$ be a positive integer and consider $\{0,1\}^n$. We define the Hamming distance $d_H(x,y)$ of members $x,y\in\{0,1\}^n$ by $$d_H(x,y)=|\big\{i\in\{0,\ldots,n-1\}:x(i)\neq y(i)\big\}|.$$
For ...
- 45.4k
4
votes
1
answer
378
views
Mathematical Structure and Objects Induced by Pairs of Disjoint Subsets
Let $\mathcal{S}$ be a finite, discrete and non-empty set, i.e.,
$$\begin{align} \operatorname{card}\left(\mathcal{S}\right) & =:n\in\mathbb{N}^+\\ V& :=\{v\subset\mathcal{S}\ |\ v\ne\...
- 12.7k
4
votes
2
answers
410
views
What Kind of Graph is This?
I am currently developing TSP heuristics that aim at symmetrically reducing the original, complete and undirected graph.
The overarching rationale is that the reduction is done via a sequence of ...
- 12.7k
4
votes
2
answers
2k
views
Edmond's blossom algorithm for Max weight perfect matchings
Edmond's blossom algorithm computes a maximum weight matching in a general graph (https://en.wikipedia.org/wiki/Blossom_algorithm).
Many papers also reference to Edmond's blossom algorithm to compute ...
- 167
4
votes
1
answer
2k
views
Maximal acyclic subgraph
It is well known that the problem of finding a maximal acyclic subgraph of a digraph is NP-complete.
Is this the case also when the digraph is symmetric ,i.e. if $(a,b)$ is a link, then $(b,a)$ is ...
4
votes
1
answer
4k
views
exact definition of Fiedler vector
For a given N-vertex similarity graph $ G=(V,A) $ the eigenvalues of the unrenormalized (graph) Laplacian may be denoted as
$$ 0= \mu_0 \leq \mu_1 \leq ... \leq \mu_N $$
where the corresponding ...
- 143
4
votes
2
answers
300
views
Non-Cayley expander graphs
When I search about expander graphs in google I see a lot of articles about expander Cayley graphs. Now my questions are as follows:
Are all expander regular graphs are Cayley, or there is a special ...
4
votes
3
answers
336
views
Relation between diametral path and regularity of a graph
Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this:
If ...
4
votes
1
answer
327
views
Vertex-connectivity of connected, vertex-transitive graphs without $K_4$ is maximum possible
A graph is said to have optimal vertex connectivity if its vertex connectivity equals its minimum degree. According to this arXiv preprint, it was shown by Mader in (Arch. Math., 1970) and (Math. Ann.,...
- 406
4
votes
1
answer
3k
views
Is there anything similar to the four color theorem for 3-dimensional objects?
From Wikipedia:
In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more ...
- 157
4
votes
2
answers
266
views
What is the standard name of an edge-graph
Given a graph $G=(E,V)$, I construct a graph $G'$ where the vertices of $G'$ are given by the edges of $G$ and say that two edges of $G$ are neighbors in $G'$ if they have a common vertex.
Is there a ...
- 71
4
votes
2
answers
1k
views
Meaning of eigenvalue 1 and symmetry in Laplacian spectra of graphs
We often see normalized Laplacian spectra of graphs where density on eigenvalue 1 serves as an axis of symmetry, with particularly high (blue spectra in the figure) or low densities (red spectrum) ...
- 225
4
votes
2
answers
313
views
Equality-preserving embeddings of finite trees
For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...
- 437
4
votes
1
answer
223
views
Graph presentation of Lexicographic shifts
Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic ...
