Skip to main content

All Questions

Filter by
Sorted by
Tagged with
1 vote
0 answers
59 views

Bipartite Representation of a Directed Graph

I am working on a combinatorial optimization problem and have constructed a bipartite graph as a representation of a directed graph. The construction is as follows: Given an initial directed graph $G$ ...
stefanabikaram's user avatar
5 votes
1 answer
386 views

Are directed graphs with out-degree exactly 2 strongly connected with probability 1?

Consider a directed graph with out-degree exactly two with $n$ vertices $v_1, v_2 \cdots v_n$ that is constructed as follows: For each vertex $v_i$, one chooses uniformly at random two (not ...
JoshuaZ's user avatar
  • 6,969
0 votes
0 answers
36 views

A class of directed graph, when their minimal polynomial of the adjacency matrix matches the characteristic polynomial

We consider an unweighted directed simple graph, $G$, with a Hamiltonian cycle. Q. Assume that the adjacency matrix of $G$ is non-singular. Do the characteristic and minimal polynomials of the ...
ABB's user avatar
  • 4,058
1 vote
2 answers
198 views

Topology of directed graph $G$ with non-singular adjacency matrix

Given a directed graph $G$ with non-singular adjacency matrix, Q. Is there a directed subgraph $H$ in $G$ that can be represented as the union of disjoint cycles such that $H$ contains all nodes of $...
ABB's user avatar
  • 4,058
2 votes
1 answer
228 views

Name for generalization of trees to digraphs

One definition of tree in graph theory could be as follows: A tree is a(n undirected) graph for which there is a unique (undirected) path between any pair of vertices. This suggest a possible ...
Manfred Weis's user avatar
  • 13.2k
3 votes
1 answer
173 views

Subset of the vertices in a tournament

Suppose we have a directed complete graph. Can we always find a subset $S\neq \emptyset$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $\dfrac{|S|}{2}$ of the ...
Masood's user avatar
  • 169
0 votes
0 answers
51 views

Kernel perfection in some powers of cycles

Suppose I orient the edges of the power of cycle graph $G=C_n^k$ where $n=16$ and $k=4$ in such a way that all the generated cycles by the elements $1,2,3,4$ are given the standard lexical orientation....
vidyarthi's user avatar
  • 2,089
1 vote
0 answers
145 views

Misunderstanding the definition of kernel in digraphs

By Borodin–Kostochka–Woodall '97 paper, the first paragraph says that directed odd cycles do not have kernels. But, I don't get this. Like, consider any $\lfloor\frac{n}{2}\rfloor$ set of independent ...
vidyarthi's user avatar
  • 2,089
0 votes
0 answers
59 views

Maximal family of cycles in directed 3-regular graphs

Consider a finite directed 3-regular graph $G=(V,E)$ where $(v,w)\in E$ implies also that $(w,v)\in E$. I am looking for a maximal set $\mathcal{C}$ of simple cycles of length greater of equal $3$ ...
Jens Fischer's user avatar
8 votes
0 answers
459 views

Extension of Erdős-Gallai (s,t)-path theorem to directed graphs

The following is a result of Erdős-Gallai from 1959 (https://link.springer.com/article/10.1007/BF02024498): Given a 2-connected undirected unweighted graph with minimum degree at least $d$, for every ...
Nicole Wein's user avatar
9 votes
2 answers
363 views

Does a strong digraph always admit a vertex that lies on some path between $\Theta(n^2)$ pairs of vertices?

Let $G$ be a directed graph. Call a vertex $v$ in $G$ central if there exists $\Theta(n^2)$ distinct pairs of vertices $(u,w)$ such that $v$ lies on some path from $u$ to $w$. We do not care whether ...
Arnaud Casteigts's user avatar
1 vote
1 answer
143 views

Eigenvalues of directed graph with one outward edge for each vertex

I am concerned with unweighted directed graphs where each node contains exactly one edge pointing to another node, which could be itself. In other words, each row of the adjacency matrix contains one ...
user3433489's user avatar
3 votes
1 answer
103 views

Minimal digraph covering with no 2-path edge sets is of size $\left( 1 + o \left( 1 \right) \right) \log_2 \chi(G)$

The last problem in 2022 IMC Day 1 strongly correlates with graph theory. In its official solution, the fundamental approach can be rephrased as follows. Give a digraph $G=(V,E)$. We call a subset of ...
Lasting Howling's user avatar
1 vote
2 answers
106 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 ...
Nathan Owen's user avatar
3 votes
1 answer
108 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 ...
Uli Fahrenberg's user avatar
6 votes
0 answers
217 views

Maximum number of Hamilton paths in a tournament on $n$ vertices

Recall that a tournament is a directed graph $T$ such that for every pair of distinct vertices $\{v,w\}$, exactly one of the ordered pairs $(v,w)$, $(w,v)$ is an arc of $T$. A tournament is strongly ...
Gordon Royle's user avatar
  • 12.7k
1 vote
0 answers
65 views

Partitioning antidirected trees with bounded degree, such that the graph induced by the partition is a constant antidirected tree

Given a partition of the vertices of a graph, we can define an auxiliary graph which conveys information about the edges between sets of the partition. This defines a graph with vertex set equal to ...
alosc's user avatar
  • 71
1 vote
0 answers
50 views

Reference for a lemma on acyclic subgraph

Lemma. Let $D$ be a digraph. Then there exists an acyclic subdigraph $D'$ of $D$ such that the total degree (i.e. out-degree plus in-degree) of $v$ in $D'$ is at least the out-degree of $v$ in $D$ for ...
Salomo's user avatar
  • 121
4 votes
0 answers
59 views

Graph-class defined by matrix-like vertex-operations

Let $m$ be a positive integer. We define a (directed) graph on $m(m-1)$ vertices $$V = \bigl\{(i,j) \mid i \ne j,\, i,j\in\{1,\dots,m\}\bigr\}$$ and edges as follows: $(i,j) \in V$ is adjacent (...
Daniel Krenn's user avatar
1 vote
2 answers
1k views

Is there a formula for the number of st-dags (DAG with 1 source and 1 sink) with n vertices?

I am looking at doing some basic validation on a database of st-dags. It would be useful to have: A formula for the number of non-isomorphic st-dags with n vertices A formula for the same with n ...
Marcel's user avatar
  • 21
0 votes
0 answers
125 views

Are there any necessary conditions of the existence of a Hamiltonian cycle on directed graphs

I'm trying to prove that one concrete directed graph has no Hamiltonian cycle, but didn't seem to find any relevant theorems
Anđela Todorović's user avatar
2 votes
1 answer
156 views

Directed version of this lemma

On a paper by Shoham Letzter, available Here, there's a lemma that says as follows: Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
alosc's user avatar
  • 71
6 votes
0 answers
130 views

Minimum of sums over degree products in a directed acyclic graph

My problem is the following: we have a graph $ G=(V,E)$. Having a total ordering $ \eta $ of the nodes, we give a direction to the edges such that $ (u,v) $ is directed from $u$ to $v$ iif $ \eta(u) &...
Alt-Tab's user avatar
  • 184
4 votes
1 answer
272 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 ...
Louis D's user avatar
  • 1,701
3 votes
1 answer
374 views

Convergence on iterating a piecewise function

Given the four functions $P_1$, $P_2$, $N_1$ and $N_2$ (which together is a piecewise function) each with domain and range as shown above: Is there an explanation as to why starting at any integer (...
Math777's user avatar
  • 143
1 vote
0 answers
82 views

Name for a directed acyclic graph with no skip-level edges?

I'm looking at a specific class of DAGs, namely those DAGs such that any path from $u$ to $v$ has the same length. Informally, we don't allow "skip-level" edges. I understand these graphs ...
Jan Westerdiep's user avatar
3 votes
2 answers
2k views

Proving that every strongly connected tournament T on at least 4 vertices contains distinct vertices u, v such that T-u and T-v are strongly connected

I have a two part question: Is there a simple proof that every strongly connected tournament $T$ on $n\geq 4$ vertices contains distinct $u,v\in V(T)$ such that $T-u$ and $T-v$ are strongly connected?...
Louis D's user avatar
  • 1,701
1 vote
0 answers
158 views

Infinite recursive graphs and different ways to build them

I asked this question one week ago on MSE and has received no answer. Infinite directed graphs (graphs with countably many nodes and edges) have a number of different applications. They can be ...
user115415's user avatar
1 vote
0 answers
108 views

Kernel perfect orientations of complete graphs

How can we create a kernel perfect orientation of a complete graph? A kernel of a graph is a set of vertices in a graph $G$, which absorbs other vertices, that is, has all the vertices in its ...
vidyarthi's user avatar
  • 2,089
3 votes
2 answers
233 views

Digraphs with exactly one Eulerian tour

I’ve been thinking about the following problem from Richard Stanley’s list of bijective proof problems (2009). There, this problem is said to lack a combinatorial solution. The problem is the ...
Luz Grisales's user avatar
6 votes
1 answer
610 views

Directed graph minor theorems

In proving the graph minor theorem, Robertson and Seymour proved a stronger statement, namely that the directed graph minor theorem is true, using the definition A directed graph is a minor of ...
Stella Biderman's user avatar
0 votes
1 answer
102 views

Has it already been shown that a digraph is $k$-connected if and only if there is a set of $k$ disjoint paths between every pair of vertices? [closed]

My question concerns graph theory. There is a conjecture I know to be true, but I am not sure whether it has been proven before. It is a fairly simple result. It may be well-known; I am not sure. ...
Toothpick Anemone's user avatar
1 vote
0 answers
223 views

Expected number of directed cycle in a directed complete graph

Consider the randomized, directed complete graph G = (V, E) where for each pair of vertices u, v ∈ V, we add either the directed edge (u → v) or the directed edge (v → u) chosen uniformly at random. ...
John Cartor's user avatar
1 vote
1 answer
110 views

Distance pairs in labeled directed graph

Suppose we have a simple directed graph with $n$ nodes and $m$ edges, and we label each edge from $1$ to $m$ (with distinct labels). Define the weighted "length" of a directed path to be the maximum ...
Antimony's user avatar
  • 130
3 votes
0 answers
346 views

Terminology for transforming a directed acyclic graph into a tree

I am looking for the term of converting a directed acyclic graph (DAG) into a tree by traversing its topologically ordered nodes and copying the subtrees of the nodes with in-degree $> 1$. Such a ...
Dudi Frid's user avatar
  • 265
2 votes
0 answers
203 views

Discrete version of Helmholtz decomposition

In The curl of graphs and networks (Gustafson and Haray, 1984) it is claimed to be shown that any digraph $G$ can be decomposed as the sum of three graphs $U_1 + U_2 + U_3$, where $U_1$ is divergence-...
Jsevillamol's user avatar
1 vote
1 answer
96 views

Infinite directed paths in tournaments on $\omega$

Does every tournament on $\omega$ contain an infinite directed path that doesn't visit any vertex twice?
Dominic van der Zypen's user avatar
1 vote
1 answer
216 views

Explicit upper bound on the number of simple rooted directed graphs on 𝑛 vertices?

Harary mentioned this problem in "The number of linear, directed, rooted, and connected graphs" on p. 455, l. 3–5, but a short and crisp upper bound is missing. I believe that someone must ...
user avatar
10 votes
1 answer
370 views

When does a graph have a circular orientation? Or equivalently can anyone help me characterize this particular class of $3$-colorable perfect graphs?

Call an oriented digraph $D=(V,A)$ circular when for all $\small x,y,z\in V$ if $(x,y)\in A$ and $(y,z)\in A$ then $(z,x)\in A$ or equivalently if $D$ is any oriented digraph whose arc set is a ...
Ethan Splaver's user avatar
4 votes
2 answers
239 views

Population of P people, where each person knows K others, how many people mutually know each other

If you have a population of $P$ people, where each person knows $K$ others within the population (does not have to be mutual, i.e., if I know you, you don't necessarily know me), and $1<K<P$, ...
curiousgeorge's user avatar
4 votes
1 answer
208 views

Characterizing relations by forbidden induced subsets

Working with relations in a purely set theoretic manner i.e. as just sets of ordered pairs, we see for any relation $R$ there exists unique inclusion minimal sets $A$ and $B$ such that $R\subseteq A\...
Ethan Splaver's user avatar
1 vote
2 answers
1k views

Finding the max-value set of cycles in a weighted digraph

I am looking for the most efficient algorithm that can solve this problem: Given a directed graph with real-valued edge weights, find a set of directed cycles (no two cycles can share a vertex) that ...
Josef Ondrej's user avatar
10 votes
0 answers
438 views

When does a graph have a minimally strong orientation?

Given an asymmetric relation $A\subseteq V^2$ a digraph $D=(V,A)$ is minimally strong iff $D$ is strongly connected and for all arcs $\alpha\in A$ the digraph $D−\alpha=(V,A\setminus\{\alpha\})$ is ...
Ethan Splaver's user avatar
1 vote
0 answers
112 views

Digraphs with same number of semiwalks

This is a follow-up question to Characterisation of walk-equivalent digraphs. Question: Do there exists two directed graphs $G$ and $H$ consisting of the same number ($n$) of vertices, such that \...
Sirolf's user avatar
  • 493
1 vote
1 answer
138 views

Characterisation of walk-equivalent digraphs

Setting Let $G=(V,E)$ be an undirected graph. A walk $\pi$ in $G$ of length $k$ is a sequence of $k+1$ vertices $v_1,\ldots,v_{k+1}$ such that for each $i\in[1,k]$, $\{v_i,v_{i+1}\}\in E$. Let $H=(W,F)...
Sirolf's user avatar
  • 493
2 votes
1 answer
122 views

Two cospectral (normal) digraphs which are not orthogonal similar

Preliminaries A complex matrix $A$ is normal when $A$ and $A^*$ commute. A real matrix $A$ is normal when $A$ and $A^t$ commute. Two complex matrices $A$ and $B$ are said to be unitary similar if ...
Sirolf's user avatar
  • 493
1 vote
1 answer
1k views

Significance of the Eigenvalues of the adjacency matrix of a weighted di-graph

I'm currently running a simulation on a bunch of randomly generated points, each with two randomly selected 'partners' from the set of points. In the simulation the points try to move such that they ...
rysuds's user avatar
  • 13
6 votes
0 answers
116 views

The properties of almost all directed graphs

A mathematician on the forum previously requested a reference on human brains modelled as directed graphs. This makes sense as neurons are mostly unidirectional and I have been thinking about similar ...
Aidan Rocke's user avatar
  • 3,871
3 votes
1 answer
283 views

Latent Dirichlet allocation and properties of digamma function

In the paper Blei, D. M., Ng, A. Y., & Jordan, M. I. (2003). Latent Dirichlet Allocation. Journal of Machine Learning Research, 3(4–5), 993–1022. http://www.jmlr.org/papers/volume3/blei03a/blei03a....
sunxd's user avatar
  • 191
3 votes
0 answers
56 views

Groups that can occur as graph automorphisms of a fixed size graph

From theorem $4$ and corollary $1$ in this book we have that graph isomorphism has to do with automorphism group of a graph. We also know every group is the automorphism group of a graph by Frucht's ...
Turbo's user avatar
  • 13.9k