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,165
questions
4
votes
1
answer
217
views
Maximal number of perfect matchings that pairwise form a Hamiltonian cycle
Definition: Let $MH(n)$ be the maximal number of perfect matchings (1-regular graphs) on $n$ vertices where the union of any two perfect matchings is a Hamiltonian cycle.
Question: Is it true that $MH(...
- 3,004
4
votes
1
answer
157
views
Lifting of a spherical graph
Let us be given a topological graph $G$
on the unit sphere in $\mathbb{R}^3$
whose edges are minor arcs of great circles.
We suppose that the graph is $3$-vertex-connected
and that a pair of edges may ...
- 1,474
4
votes
1
answer
293
views
Number of walks on integer lattice with self-edge at zero
Consider the graph with vertices $V=\mathbb Z$ and edges
$$E=\{(n,n+1):n\in\mathbb Z\}\cup\{(0,0)\},$$
that is,
the usual integer lattice with a self-edge at zero.
For some fixed parameters $a,b,n\in\...
- 173
4
votes
1
answer
236
views
Self-containing trees
Suppose that $r^2-r-1=0$ and that $T$ is the tree with root $1$ such that the children of each node $x$ are $rx$ and $x+1$. Remove all duplicates as they occur, and let $T(r)$ denote the remaining ...
- 3,443
4
votes
1
answer
448
views
Generalisation of Kuratowski's theorem
So I've recently read the infinite graph version of Kuratowski's theorem. It says that a graph $G$ is planar if and only if the following three conditions holds:
$|V(G)| \le |\mathbb{R}|$
$G$ has at ...
user81529
4
votes
1
answer
262
views
Counting trees according to endpoints
Question: Is there a nice (or any) formula for the generating function
$$T(x,y) = \sum_{m,n} t_{m,n} x^my^n,$$
where $t_{m,n}$ is the number of trees with $m$ vertices and $n$ endpoints?
...
- 1,401
4
votes
1
answer
135
views
Dense high-degree sub-graphs of dense graphs
Let $G$ be a graph with $n$ vertices and $m$ edges, and let $d=\lfloor\frac{m}{n}\rfloor$ be the rounded-down average-degree. A lemma that is attributed to Erdos says that $G$ has a non-empty induced ...
- 419
4
votes
1
answer
167
views
Are there 2-connected regular graphs whose maximum matching leaves 3 vertices uncovered?
I'd like to use Corollary 5 of a paper by Hell & Kirkpatrick on graph packings to obtain an NP-hardness result. They want a 2-vertex-connected graph $F$ such that every matching in $F$ leaves at ...
- 143
4
votes
1
answer
181
views
Product of geodesic distances
I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. ...
- 143
4
votes
2
answers
212
views
Are the following Cayley digraphs Hamiltonian?
Consider the Cayley graphs $A'G_n$ on the alternating group $A_n$ with generating set $S = \{(1i2) : 3 \leq i \leq n\}$, for $n \geq 4$.
See the following page on Alternating Group Graphs for ...
- 61
4
votes
1
answer
720
views
Minimum distance between Hamiltonian cycles in cubic Hamiltonian graph
It is $NP$-hard to find constant factor approximation of longest cycle in cubic Hamiltonian graphs. Therefore, finding a Hamiltonian cycle in a cubic Hamiltonian graph is NP-hard.
By Smith's theorem, ...
- 2,951
4
votes
2
answers
205
views
Jordan-like cycles in graphs
[Added another complementary question below.]
Motivation
The 1-skeleton of the triangular bipyramid seems to be the smallest connected planar graph $G$ with the following
Property: There is a cycle $\...
- 9,628
4
votes
1
answer
629
views
Combinatorial geodesics
[There has been a flaw in my definition - as Sergei and Andreas pointed out. I hope I could fix it.]
I want to understand how the concepts of directions, straight (or shortest) lines, and geodesics &...
- 9,628
4
votes
2
answers
315
views
Shannon capacity determined by $\alpha(G)$ and $\chi^*(\bar{G})$???
Are there graphs where $\alpha(G) = \chi^*(\bar{G}) < \chi(\bar{G})$???
Here, $\chi^*(\bar{G})$ is the fractional chromatic number, which I believe is also equal to the fractional independence ...
- 405
4
votes
1
answer
201
views
Counting graphs with diameter d
Is there some known sequence which gives me the number of graphs with diameter d?
Similarly is there some 2D-sequence which gives me the number of graphs with n vertices and diameter d?
If there is ...
- 75
4
votes
1
answer
500
views
Graph Theory: 2012 ARML Power Question - references?
The definition of the Workday Number of a finite graph is given on page 14 in http://www.arml.com/2012_contest/2012_Contest_Final_Version.pdf and the rest of the problem statement is given at the top ...
- 43
4
votes
2
answers
2k
views
Regular graph colorings
[Since I didn't get any feedback at MSE, I dare to post this question here, too.]
Call a coloring $C:V(G) \rightarrow \lbrace 1,\dots,n \rbrace$ of a graph $G$ regular when every vertex with color $...
- 9,628
4
votes
1
answer
312
views
Representing groups with two generators as graph automorphisms
Suppose we have a group $G$ which can be generated by two elements $x$, $y$. Call $H$, $K$, $L$ the subgroups of $G$ generated by $x$, $y$ and $y^{-1}x^{-1}$, respectively.
With these data, we can ...
- 2,517
4
votes
2
answers
2k
views
Simple uses for the Entropy bound on the volume of a Hamming ball
I'm a teaching assistant in an introductory course of Information Theory. I intend to prove the following well-known fact that easily proven using elementary information theoretic consideration:
$\...
- 327
4
votes
1
answer
925
views
Solving for Hamiltonian path with constraints on allowable routes through vertices
Suppose you have a complete graph with N vertexes, with a distinguished vertex $n=1$ ("start"), and you wish to find a route traveling exactly once through each vertex so that the distance along the ...
4
votes
1
answer
633
views
What packages for subgraph enumeration are available?
In learning about network motifs, I discover claims that Mfinder (circa 2004) is the "the first motif-mining tool" (Kashani et al. 2009). Motifs are connected induced subgraphs that occur more ...
- 4,209
4
votes
1
answer
573
views
Bounds on strong vertex colourings of regular hypergraphs?
What are the best results for upper bounds on the number of colours required in a strong vertex colouring of a regular hypergraph H?
A regular hypergraph is one in which every vertex is contained in ...
- 1,394
4
votes
1
answer
863
views
characterization of trees in terms of products of transpositions
Suppose a simple graph has $n$ vertices and $m$ edges. If the vertices are labelled, then each edge then corresponds to a transposition in a natural way. A theorem in Godsil and Royle's Algebraic ...
- 43
4
votes
1
answer
201
views
Erdős–Rényi random graphs — reproducing 2 inequalities
In Erdős and Renyi's 1959 paper On random graphs I
, I'm trying to reproduce, starting from Eq.\eqref{1} in their paper, the two inequalities that appear in Eq.\eqref{2}.
Eq.\eqref{1} is:
$$
P \le \...
- 43
4
votes
2
answers
190
views
Algorithm for grouping tetrahedra from Voronoi diagram
I have a set of 3D Voronoi generator points and their neighbouring points, which, when connected, should result in a Delaunay tetrahedralization. However, I'm having a hard time implementing this. My ...
- 142
4
votes
1
answer
173
views
Quasi-random vs pseudo-random graphs
My question is somehow concerning terminology on extremal graph theory.
Is there any difference concerning the notion of quasi-random graph and the notion of pseudo-random graph? My feeling is that ...
- 1,543
4
votes
2
answers
263
views
Intuition on inequality in proving a bound on the sum of squares of degrees of a graph
Given a simple connected graph $G$ with $n$ vertices and $m$ edges, let $d_1, ..., d_n$ denote the degrees of the vertices of the graph. In this very short paper, the author prove the inequality
$$\...
- 652
4
votes
1
answer
408
views
Construction of graphs of high girth and chromatic number
Are there any concrete constructions of graphs of both high girth and chromatic number?
Of course there is the seminal paper of Erdős which proves the existence of such graphs via the probabilistic ...
- 128
4
votes
1
answer
493
views
Random graphs and Benjamini-Schramm convergence
I am looking for literature on the question whether a randomly chosen sequence of $k$-regular graphs converges in the Benjamini-Schramm sense to the universal covering with probability one.
There are ...
user130903
4
votes
2
answers
574
views
Co-trees of a simple graph
Consider fundamental cycles (say $k$ of them) of a specific spanning tree of a simple graph (with $m$ edges) which is also connected and has no one-edge bonds.
Make the graph directed (in an arbitrary ...
- 419
4
votes
1
answer
183
views
Number of permutations with combinatorial geometric constraints
We are given a $d$-dimensional hypercube $H$, where each vertex is labeled with an integer $\ell\in\{1, 2, \ldots, 2^d\}$. Let $L$ be this labelling.
Question: How many labelling permutations $L'$ of ...
- 1,677
4
votes
1
answer
253
views
Dominating sets in subtournaments of the Paley tournament
For a tournament $T$, let $\mathrm{dom}(T)$ be the order of a smallest dominating set in $T$. Let $q$ be a prime power congruent to 3 mod 4 and let $T_q$ be the Paley tournament on $q$ vertices.
Is ...
- 1,666
4
votes
1
answer
321
views
Minimally separating graphs
We say that a simple, undirected graph $G=(V,E)$ is separating if for all $x\neq y\in V$ there are $e_x,e_y\in E$ such that $x\in e_x$ and $y\in e_y$, and $e_x\cap e_y = \varnothing$. We say $G$ is ...
- 45.5k
4
votes
1
answer
271
views
Structures for random graphs with structure
Background[You may skip this and go immediately to the Definitions.]
Crucial features of a (random) graph or network are:
the degree distribution $p(d)$ (exponential, Poisson, or power law)
the mean ...
- 9,628
4
votes
1
answer
330
views
Relation between Kirchhoff's Circuital law and Matrix tree Theorem
I'm not a professional mathematician, just an undergraduate student. I was reading Introduction to Graph Theory by West, I came over the topic which discuses the methods to find the spanning trees in ...
- 143
4
votes
1
answer
136
views
Counting adjacency matrices
Here is a question that has come up in the context of a problem that involves counting partially ordered sets.
For an adjacency matrix $A$, let $p$ be the sum of elements in the strict upper ...
- 192
4
votes
1
answer
169
views
Hamiltonian paths on the space of graphs
Disclaimer: I am not a professional graph theorist.
Motivation:
Let's consider the set $G_N$ of graphs with $N$ vertices where the vertices are assumed to be distinguishable. This set may ...
- 3,827
4
votes
1
answer
234
views
Graphs with adjacency matrix depending on associated-vector distances
Let $G$ be a graph of order $n$ such that for each vertex $v$ there are two associated vectors, $f_v, g_v\in R^n$, where $uv\in E(G)$ if and only if $\|f_u - f_v\|^2 \ge \|g_u-g_v\|^2$.
ISGCI didn't ...
- 519
4
votes
1
answer
174
views
Origin of the relations of Leavitt path algebras
I know the formal definition of Leavitt path algebras, but I want know why the relations defining Leavitt Path Algebras are defined in that way? what is special of this relations?
My real hidden ...
- 51
4
votes
1
answer
135
views
Hamming representability of finite graphs
This is a follow up on an older question.
We construct graph on the vertex set $\{0,1\}^n$ where $n$ is a positive integer. For $x,y \in \{0,1\}^n$ the Hamming distance of $x,y$ is the cardinality of ...
- 45.5k
4
votes
1
answer
178
views
Cliques in Cayley graph on $n$-cycles
Let $S\subset S_n$ be the set of all $n$-cycles. I want to know if the Cayley graph $(S_n,S)$ has large dense subgraphs. I'm expecting it to not have super-polynomial size and $1-o(1)$ dense subgraphs....
- 203
4
votes
4
answers
265
views
Bijective operations on finite simple graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I am interested in specific bijective maps $\mathcal G_n\to\mathcal G_n$, defined for all $n$. An ...
- 5,563
4
votes
1
answer
182
views
$\{ P_3, P_4 \}$-factor
Definition. A graph $G=(V,E)$ is to be $\{d_1,\dots,d_n\}$-graph if for each vertex $v\in V$ we have $\text{deg}(v)=d_i$ for some $i=1,\dots n$.
Definition. A connected graph $G=(V,E)$ is called $...
- 41
4
votes
1
answer
262
views
Transfer-impedance matrix for edge correlations in random spanning tree
Suppose $G$ is a (weighted) connected graph and
let $T$ denote a random spanning tree of $G$,
chosen uniformly (or respecting the edge weights).
It is known that for any distinct edges $e, f$
$$\...
- 2,125
4
votes
2
answers
220
views
Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?
Given two digraphs $G$ and $H$, I want a method for creating a bijection between all non-simple cycles of for all $n \le |V(G)|$. That means, given $C_G(n)$ and $C_H(n)$ being the sets of all non-...
- 71
4
votes
1
answer
153
views
Posets as graphs with the direct neighbor relation
Given any poset $(P,\leq)$ we define the "direct neighbor graph" as follows. Let $$E_P = \big\{\{a,b\}: (a<b \text{ or } a>b) \text{ and } \; ]\min\{a,b\},\max\{a,b\}[ = \emptyset\big\}.$$
It is ...
- 45.5k
4
votes
1
answer
75
views
Existence of optimal tours containing an 'extremal' edge
let $\mathcal{P}$ be a finite set of points in the euclidean plane in general position, and let $$\lbrace p_A,p_B,p_C,p_D\rbrace: \ \|p_C-p_A\|+\|p_D-p_B\|\ \gt \|p_i-p_h\|+\|p_k-p_j\|\quad\forall\ \...
- 12.7k
4
votes
1
answer
298
views
A Geometric Combinatorial/Graph Theory Question
I have a combinatorics problem that seems pretty general - I'd be surprised if the answer is not known. Unfortunately, I can't seem to solve it.
The question concerns the following situation: ...
- 409
4
votes
2
answers
232
views
Girth vs. largest induced acyclic subgraph
I have a hopefully quick reference question. Given n vertex digraph G of out-degree T, and no 2 cycles (girth at least 3), what is the lower bound on number of vertices in the largest induced acyclic ...
- 41
4
votes
1
answer
308
views
Infinite Tree with Poisson Clocks
Let $\mathcal{T}$ be the infinite countable $3$-regular tree graph. Pick a vertex in this graph, call it the root. Let the root carry the value $0$.
Next, assign $1$ to the neighbours of the root. ...
- 403