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.

Filter by
Sorted by
Tagged with
0 votes
0 answers
4 views

Hamiltonian cycle in bike-lock graph with $1$ known digit

Motivation. My youngest son has a bike lock with dials, and he forgot the unlocking combination completely, except that he remembered that digit $0$ appeared somewhere in the combination. So it was my ...
user avatar
0 votes
0 answers
18 views

Existence of perfect "sub-matchings" in symmetric bipartite regular graphs

Given a symmetric $k$-regular assignment matrix $\boldsymbol{A}\in\lbrace 0,1\rbrace^{r\cdot s\,\times r\cdot s}$ that is "partitioned" into submatrices of size $r\times r$. The existence of ...
user avatar
4 votes
1 answer
104 views

Strongly minimal covers for clique hypergraphs of graphs

$\DeclareMathOperator\Cliq{Cliq}$A hypergraph $H$ is a pair consisting of a set $V$ of vertices and a family of subsets of $V$ called edges. One class of examples is obtained by taking a graph $G=(V,E)...
user avatar
  • 1,064
4 votes
1 answer
102 views

Find all 2-planar drawings of $K_6$ and $K_7$

A $k$-planar graph is a graph which can be embedded with at most $k$ crossings per edge. It is proved that a complete graph $K_n$ is 2-planar if and only if $n\le 7$. Angelini P., Bekos M. A., ...
user avatar
2 votes
1 answer
59 views

Counting Euler circuits through labelled trees where $v_1$ and $v_2$ have distance two

Let $T_n$ be the set of all labelled trees with $n$ vertices. For any $T \in T_n$ let $D(T)$ be the 'doubled tree', where each edge of $T$ is replaced by one directed edge in each direction. $D(T)$ is ...
user avatar
  • 343
1 vote
0 answers
94 views

Hamilton decomposition for infinite Cayley graphs

We have a finitely generated group $G$ which is infinite. Does there exist such a finite generating set $S$, $G= \langle S\rangle$, that the corresponding Cayley graph $\mathrm{Cayley}(G,S)$ can be ...
user avatar
0 votes
0 answers
34 views

Find number of overlapping edges in a one-dimensional graph

I have a set of edges $(v_1, v_2), (v_2, v_3),(v_2, v_4)$ where each edge has a weight. Say the weights are 1, 2 and 3 respectively. Then we can visualise it as 3 threads, where the the thread from ...
user avatar
0 votes
0 answers
60 views

Optimal covering trails in 3 and 4 dimensions

A couple of years ago, I constructively solved (inside the $AABB$ $[0,3]$ X $[0,3]$ X ... X $[0,3]$) the $k$-dimensional generalization of the infamous Nine-Dot Problem by S. Loyd (see Cyclopedia of ...
user avatar
  • 1
2 votes
1 answer
142 views

What is the name of a matrix operation using the OR operator instead of addition?

Let's say we have two matrices $M$ and $G$ with $G, M \in \{0, 1\}^{n, n}$, we denote by $m_{i, j}$ the element of $M$ in the $i^\text{th}$ row and $j^\text{th}$ column, same for $G_{i, j}$. Let's ...
user avatar
  • 31
2 votes
1 answer
128 views

Can ZFC sets be interpreted as single rooted trees with accessible degree and countable height?

Let $T$ be a single directed tree, by parameters $(\kappa, \lambda, \zeta)$ of $T$ we mean: the number of root nodes in $T$, the strict upper bound on the number of children nodes per a node in $T$, ...
user avatar
0 votes
0 answers
60 views

Expectation of edge weights on the complete graph, Part 2

This question concerns the same basic set-up as my previous question: Expectation of edge weights on the complete graph In that question an answer was given which shows that the expected value is as ...
user avatar
1 vote
1 answer
131 views

Expectation of edge weights on the complete graph

Let $n,k \geq 3$ be positive integers with $n$ much larger than $k$ and consider a random assignment of weights to the edges of the complete graph $K_n$. On each vertex of $K_n$ we attach a random ...
user avatar
0 votes
0 answers
53 views

Determining the total number of nonzero expansion terms in a (0,1)-matrix

Let $A=(a_{ij})_{n\times n}$ be a $(0,1)$-matrix such that it contains equal number of $1$s in each row and column. Is there any general method to count the total number of the nonzero terms $\prod_{i=...
user avatar
  • 133
7 votes
2 answers
182 views

Does entropy of the random walk control the return probability

Given an infinite connected graph $G$ of bounded degree with vertex set $X$, let $P_x^n$ the time $n$ distribution of the simple random walk started at the vertex $x$ (so $P^n_x(y)$ is the probability ...
user avatar
  • 4,214
1 vote
0 answers
49 views

Number of eulerian subgraphs of complete graph [closed]

I need an advice on how to approach this problem. It's a part of a project in Graph theory. How to determine a number of eulerian subgraphs of $K_n$ (complete graph with $n$ vertices)? It's part of a ...
user avatar
  • 11
-1 votes
1 answer
95 views

Are all subdivisions of bipartite graphs also bipartite?

Excuse the poor quality image, but it illustrates my point well enough. I couldn't find the answer anywhere else online.
user avatar
11 votes
1 answer
212 views

Infinite vertex-transitive graph where every automorphism has a fixed vertex

This is a follow-up to the question Connected vertex-transitive graph with the fixed-point property. In particular, it is based on a comment by user bof. Let $G = (V,E)$ be a graph with $V$ infinite. ...
user avatar
  • 18.8k
2 votes
0 answers
35 views

Definition of sectional curvature of graph and relation to smooth sectional curvature

Let $(M,g)$ be a Riemannian manifold. Let $\tau$ be a triangulation, i.e. a simplicial complex together with a fixed homeomorphism to $M$. By forgetting about all cells except $0$-cells and $1$-cells ...
user avatar
5 votes
1 answer
315 views

Connected vertex-transitive graph with the fixed-point property

Many connected vertex-transitive graphs $G=(V,E)$ have the property that some of their automorphisms other than the identity have fixed points. To point out two simple examples: If $G = K_3$ then the ...
user avatar
9 votes
3 answers
292 views

Is it possible that every edge in a 1-planar drawing with minimum number of crossings is crossed?

A graph is 1-planar is it has drawing in the plane so that each edge is crossed at most once. Here we also assume the drawing satisfies (1) no edge is self-crossed; (2) no two adjacent edges are ...
user avatar
6 votes
0 answers
75 views

Maximum number of cycles on regular graphs

Let $G$ be a $d$-regular graph on $n$ vertices. I'm interested in upper bounds on the number of cycles of length $k$ that hold for any such $G$. The regime I'm interested in is: $d$ is fixed, and $...
user avatar
1 vote
2 answers
61 views

Minimum edge-weighted directed subgraph in polynomial time

I am looking for an algorithm with polynomial complexity where, given a strongly connected edge-weighted digraph I can find the minimal subgraph which connects some root vertex v to a known set of ...
user avatar
1 vote
0 answers
64 views

Counting number of spanning trees of the complete bipartite with given vertex-degrees

For given $n_1,n_2 \in \mathbb{N}$ let $K_{n_1,n_2}$ be the complete bipartite graph. I have seen a few sources proving that the number of spanning trees $t(K_{n_1,n_2})$ is given by $n_1^{n_2-1} n_2^{...
user avatar
  • 343
4 votes
2 answers
118 views

Connecting $2n$ points in $\mathbb R^2$ with line segments s.t. each point belongs to exactly one line segment

I'm trying to do a certain simulation related to the toric code and I'm looking for an algorithm that connects $2n$ points ($n \in \mathbb Z_+$) in $\mathbb R^2$ with line segments with the following ...
user avatar
2 votes
1 answer
159 views

Is there a formula for the number of trees with this extra condition?

A tree $G$ on $n$ vertices $V=\{v_1,...,v_n\}$ is a connected undirected graph which is acyclic. For each tree $G$ one can split the set of vertices $V$ into two disjoint subsets $U,W \subset V$ such ...
user avatar
  • 343
5 votes
2 answers
206 views

Why is the spectrum of Erdős–Renyi random graph approximately symmetric?

I am recently self-learning random matrix theory and made some simulations about the spectrum of Erdős–Renyi random graph $G(n,p)$ when $np\to\infty$, and $np\to c=2,3$. The plots above are already ...
user avatar
  • 433
0 votes
0 answers
17 views

generalized transitive reduction of a directed graph

The transitive reduction of a graph $G$ is a graph with the same vertices that preserves reachability: a path from $a$ to $b$ exists in the reduced graph if and only if one exists in the original ...
user avatar
  • 131
0 votes
1 answer
74 views

Non-linear diffusion on networks

The diffusion equation with constant diffusion $D$ can be represented as: \begin{equation} \frac{\partial \phi(r, t)}{\partial t}=D \Delta \phi(r, t) \end{equation} where $\Delta$ is the Laplace ...
user avatar
  • 125
12 votes
3 answers
2k views

Is there any fast implementation of four color theorem in Python?

I'm now using scipy.spatial.Voronoi to generate a Voronoi graph, as shown here: voronoi graph. I'd like to apply the four color theorem on it, so that no adjcent regions share the same color. I ...
user avatar
  • 129
5 votes
0 answers
92 views

How to construct 4-regular graphs with few Hamiltonian decompositions?

A Hamiltonian decomposition of a finite simple graph is a partition of its edge set so that each partition class forms a Hamiltonian cycle. This is only possible if the graph is $2k$-regular. ...
user avatar
  • 9,471
0 votes
1 answer
91 views

List coloring as a homomorphism

A proper coloring of the vertices of a graph $G$ is seen as a homomorphism from the graph vertices to the complete graph on the number of vertices equal to the chromatic number of the graph. ...
user avatar
  • 1,611
12 votes
0 answers
219 views

Computing the number of ways to delete vertices sequentially without disconnecting a graph

Given a finite connected graph on $n$ vertices, we are trying to count the number of ways to label the vertices $1$ to $n$ so that deleting them sequentially in that order never disconnects the graph. ...
user avatar
5 votes
1 answer
145 views

Is the crossing number of the line graph of $K_5$ determined?

The line graph of an undirected graph $G$ is another graph $L(G)$ that represents the adjacencies between edges of $G$. $L(G)$ is constructed in the following way: for each edge in $G$, make a vertex ...
user avatar
2 votes
2 answers
109 views

Odd partition with extra properties

Can such a set $A=$ {$a_1,.. a_k$} exist, such that: $\sum_i a_i = 1$ and $a_i $ are rational positive numbers $k$ is and odd number, and is at least $3$. We can partition $A$ in two parts of value $...
user avatar
  • 75
5 votes
1 answer
80 views

Is there any relationships between path cover number and chromatic number?

Let G be a finite simple graph. Consider the independent number $\alpha$, the chromatic number $\chi$ and the path cover number (also called the path partition number) $\rho$. Then we have $\alpha\chi ...
user avatar
  • 376
1 vote
0 answers
41 views

Standard test for the recognition of toroidal graphs

Is there a standard test for the recognition of toroidal graphs? I have been using the Boyer–Myrvold planarity algorithm, which has a MATLAB and C++ implementation.
user avatar
  • 11
3 votes
0 answers
81 views

Digraph without "immediately isomorphic" vertices?

Say that a digraph $(V,E)$ is reducible if there exist $x,y\in V$ with $x\ne y$ and such that for all $z\in V$, $(x,z)\in E\leftrightarrow(y,z)\in E$ and $(z,x)\in E\leftrightarrow(z,y)\in E$. It is ...
user avatar
0 votes
0 answers
41 views

Show that two matrices are strongly shift equivalent

The following question is from Introduction to dynamical systems, written by Michael Brin and Garrett Stuclk. Given two non-negative integer square matrices $A, B$, we say $A, B$ are elementarily ...
user avatar
3 votes
1 answer
65 views

Property of the spanning tree with minimal leaves

Let $G$ be a connected simple graph. For any spanning tree $T$ of $G$, let $l(T)$ be the number of leaves of the graph $T$. Consider $\ell=\min_Tl(T)$, can I find a spanning tree $T$ with $l(T)=\ell$, ...
user avatar
  • 376
2 votes
0 answers
41 views

Maximize connectivity probability with a number of edges

We are given a graph $G$, whose edges are either open or closed. Initially all the edges are closed. For each edge $e$, if we choose to activate it, then after the activation, it becomes open with ...
user avatar
  • 491
0 votes
0 answers
50 views

Graph reduction and combinatorial optimization

Crossposted at Theoretical Computer Science SE We are given a multigraph $G$. Consider two nodes $u$ and $v$ with multiple edges between them. Each elementary edge is associated with a metric called ...
user avatar
  • 491
0 votes
1 answer
55 views

Convergence of the average weight of an infinite path through a weighted directed graph

Consider a directed graph $G = (V, E, w)$, where $V$ is the set of vertices, $E \subseteq V \times V$ is the set of directed edges (with self-loops allowed), and $w : E \to \mathbb{R}_+$ is a weight ...
user avatar
  • 1
6 votes
0 answers
134 views

Lindström-Gessel-Viennot from properties of the $Alt^k$ functor?

Let $A$ be the directed adjacency matrix of an acyclic directed graph, with variables as its nonzero entries (one for each edge). The $(a,b)$ entry of the matrix $(I-A)^{-1}$ is the sum over all paths ...
user avatar
1 vote
0 answers
43 views

Angles between edges of a geometric graph and graph invariants

Are there any clever ways in which the angles between edges in a geometric graph are encoded in the graph spectrum, or another object associated with the graph? I'm interested to see what else is ...
user avatar
  • 466
5 votes
3 answers
185 views

Probability of an edge in a random graph

Consider a vertex set $V$ and a degree sequence $(d_v)_{v\in V}$. I want to know the probability that an edge exists between two given vertices $u$ and $v$ in a random graph with this degree sequence. ...
user avatar
4 votes
0 answers
91 views

When is a Schreier coset graph vertex transitive

When is a Schreier Coset graph on a group $G$ with subgroup $H$ and symmetric generating set $S$(without identity) vertex transitive? It is well known that when $H$ is normal, the Schreier coset graph ...
user avatar
  • 1,611
3 votes
0 answers
99 views

Free $2$-category on a $2$-quiver

The construction of the free category on a quiver is standard in category theory. Is there some $2$-dimensional analog of a quiver such that each $2$-quiver freely gives rise to a $2$-category? How ...
user avatar
  • 6,211
2 votes
1 answer
63 views

Efficient algorithm for edge-coloring complete graphs

Edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color with an optimal number of colors. Two edges are said to be adjacent if ...
user avatar
  • 982
0 votes
0 answers
81 views

Does an extension of the B.E.S.T. theorem for multiple Eulerian circuits exist?

Given a directed multigraph $G=(V,E)$ (multiple edges and loops are permitted) the number of distinct Eulerian circuits for $G$ can be calculated with the B.E.S.T. theorem. Does a similar theory for ...
user avatar
  • 343
0 votes
0 answers
23 views

Examples of Post Correspondence Problem (PCP) used to prove undecidability in graph theory

I am looking for interesting papers that use a reduction to PCP in order to prove undecidability of certain problems relating to graph theory. Specifically I'm interested in ways in which PCP is ...
user avatar
  • 101

1
2 3 4 5
93