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,150
questions
4
votes
2
answers
1k
views
Probability distribution over cluster size in Erdős–Rényi random graph.
My question is about the probability distribution over the possible size of the containing cluster of a randomly chosen node in an Erdős–Rényi random graph.
Let G(n,p) be an Erdős–Rényi random graph (...
4
votes
1
answer
262
views
what's an upper bound on the size of the largest biclique in random bipartite graph?
I am not an expert in random graph but I need the following result and I couldn't find any reference on this.
Let $G(X \cup Y,p)$ be a random bipartite graph where the set of edges is $X \cup Y$, $X$ ...
4
votes
1
answer
538
views
Graph connectivity related game
I was considering the following game on an undirected unweighted graph $G=(V,E)$ (not necessarily simple). Two players, Police and Runaway, take moves in turn. Police can cut an arbitrary subset of ...
4
votes
1
answer
4k
views
Finding a vertex of least distance to all other vertices in a graph
Some background to my question: if $G$ is a (simple) graph of $N$ vertices, labelled by integers $0,1,...,N-1$, the closeness centrality of a vertex $i$, denoted by $C(i)$, is defined to be the ...
4
votes
2
answers
652
views
# bridges in random connected graph
Suppose we have an Erdos random graph with $n$ vertices and $c n$ edges.
What can you say about the probability that the graph is connected?
(More importantly) If it is connected, what is the ...
4
votes
1
answer
154
views
Probability problem in Sheehan's conjecture
As my first math project, I have been working on Sheehan's Conjecture
and am stuck for weeks. I wonder if I am at a dead end.
Sheehan's Conjecture states that every Hamiltonian 4-regular simple
graph ...
4
votes
1
answer
104
views
Are there decompositions of $K_{16}$ by certain 3-regular graphs?
This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering:
Can the (edges ...
4
votes
1
answer
307
views
The upper bound of edges of the generalized cactus graphs
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, it is a connected graph in which every edge belongs to at most one simple ...
4
votes
1
answer
126
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)...
4
votes
1
answer
168
views
Explicit constructions of regular graphs with very sparse induced subgraphs
Let $d\ge 3$ be a constant. Is there an explicit construction of an infinite family of $d$-regular graphs such that for $G$ in this family with $n$ vertices, every subgraph $H$ of on at most $\alpha n$...
4
votes
1
answer
188
views
Can't lower bound be improved on number of light edges in planar graph with minimum degree five?
Let an $i$-vertex be a vertex of degree $i$. Let an $i, j-$ edge be an edge joining an $i-$vertex to
a $j-$vertex. Given a plane graph G, let $e_{i,j}$ be the number of $i, j-$edges of $G$.
I found ...
4
votes
1
answer
135
views
Finding minimum weight perfect matchings in sparse bipartite graphs
Question:
What can be recommended for finding optimal perfect matchings in large bipartite graphs with small vertex degree if the edge-weights are positive real values?
I am looking for ...
4
votes
1
answer
157
views
Automated rewriting of string diagrams in symmetric monoidal categories
Many algebraic structures, such as Frobenius algebras, or quasi-triangular Hopf algebras, can be formulated in an arbitrary symmetric monoidal category. They are given by a collection of morphisms, ...
4
votes
1
answer
355
views
Turan numbers of r-partite hypergraphs
Let $H$ be a balanced $r$-partite $r$-uniform hypergraph with $nr$ vertices. (Each part of this hypergraph consists of $n$ vertices; every hyperedge has exactly one vertex in each part.) Denote a ...
4
votes
1
answer
312
views
Planar duality generalized to embedded simplicial complexes
Let $K$ be a finite $d$-dimensional simplicial complex embedded in $\mathbb{R}^{d+1}$. The setting of this question is simplicial homology with coefficients over $\mathbb{Z}_2$. By Alexander duality $...
4
votes
1
answer
631
views
Algorithm to generate free unlabelled trees uniformly at random
I am implementing an algorithm to generate free unlabelled trees uniformly at random (uar). For this I found this paper by Herbert S. Wilf (The uniform selection of trees. 1981. In Journal of ...
4
votes
1
answer
145
views
Almost all simple graphs are small world networks
Two days ago it occurred to me that almost all simple graphs are small world networks in the sense that if $G_N$ is a simple graph with $N$ nodes sampled from the Erdös-Rényi random graph distribution ...
4
votes
1
answer
582
views
Martingales and intersection of random walks
Let $G=(V,E)$ be a graph with $n$ vertices. Consider a pair of independent simple random walks $(X,Y)$ on the graph, each of length $L$ starting from a node $v \in V$. We denote a length-$L$ random ...
4
votes
1
answer
191
views
Most adequate software for proof checking graph theory proofs
What might be the best software for checking the validity of proofs of graph theoretical statements? Lean, HOL, ... ? One criterion would also be, what would be the easiest for a graph theorist to ...
4
votes
1
answer
233
views
Total coloring conjecture for Cayley graphs
The total coloring conjecture (TCC) states that any total coloring of a simple graph $G(V,E)$ has its total chromatic number bounded as $\chi^{T}(G)\le \Delta+2$ where $\Delta $ is the maximal degree ...
4
votes
1
answer
138
views
Asymptotic colouring of edges and vertices, and untwisting cocycles
This question regards colourings on edges and vertices on countable directed multigraphs.
We start with an example. Let $G=\mathbb Z^2$. We define two functions $a_h$ and $a_v$ from $\mathbb Z^2$ to $\...
4
votes
1
answer
158
views
Dynamics for approximating harmonic functions on graphs
A harmonic function on a graph is a function on its vertices such that the value at every vertex is the average of the values at its neighbors.
Consider the following method for approximating a ...
4
votes
1
answer
772
views
The generic nullspace of a graph
Let $A$ be a matrix whose entries are either indeterminates or fixed to zero. For example, consider
$$A = \left( \begin{array}{ccc} 0 & x_{12} & 0 \\
0 & 0 & 0 \\
0 & x_{32} & ...
4
votes
1
answer
170
views
Minimal size of the maximal biclique
We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each node on side $R$ is connected to $k$ nodes on side $L$, ...
4
votes
1
answer
1k
views
What is the minimum diameter of $r$-regular, $k$-connected graphs?
Let $md_r^k(n)$ be the minimum diameter over all $r$-regular, $k$-connected graphs on at least $n$ vertices. (Let us assume $r, k \geq 2$).
Problem: Find lower and upper asymptotic bounds on $md_r^...
4
votes
1
answer
182
views
Base decomposition of matroids
I want to find a generalization of the idea that, in a graphic matroid, every base can be decomposed on the stars (edges adjacent to a vertex).
For example one could say that a matroid $M$ of rank $k$...
4
votes
1
answer
205
views
Representing a graph's vertices as linear combinations of paths
I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in ...
4
votes
2
answers
391
views
What is the independence number of this graph which is a generalization of a Kneser graph?
Let $\mathfrak{A}=\{1,2,\dots,8\}$ and construct a graph as follows. Let the vertices of the graph be the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ are distinct. Two ...
4
votes
1
answer
159
views
Show existence maximal clique of order $s$ in an multigraph where each vertex is colored with a set of colors
You are given a multigraph $G$ with $n$ vertices as follows:
$V := (v_1, v_2, \dots ,v_n)$
$C := \{c_1, c_2, \dots\}$, be an infinite set of colors.
$f: V \rightarrow \mathbb{P}_{\le m}(C) $, a ...
4
votes
1
answer
567
views
inequality with exponents
We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v \...
4
votes
1
answer
649
views
Embedding graphs into hyperbolic spaces
Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...
4
votes
1
answer
523
views
Connection between connectivity and cohesion of a graph
Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path.
A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...
4
votes
1
answer
69
views
Balancing out edge multiplicites in a graph
Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge).
Is there some simple graph $H$ such that the $t$-fold ...
4
votes
1
answer
134
views
Graph Verification Problem
Does anyone know whether the following problem has been solved or has an easy solution?
Given a graph $(V,E)$, two subsets of the vertices $U_1=\{u_1, \dots, u_r \}, U_2=\{v_1, \dots, v_s \} \subset ...
4
votes
1
answer
294
views
NP-hardness of sparsest cut
Consider bipartitioning the vertices of a graph $(V,E)$ into $V = P \cup Q$ to minimize $$\frac{|E(P,Q)|}{|P| |Q|},$$ where $E(P,Q)$ denotes the set of edges in the cut. The usual citation for NP-...
4
votes
1
answer
192
views
the minimum possible value of the order of a graph G which is a finite union of N-order complete graphs
Let $N$ be a positive integer,$G$ be a simple graph and $H_1,H_2,\ldots,H_k$ be a family of subgraphs of $G$ which satisfy:
every $H_i$ is a $N$-order complete graph;
the union of $H_i$ is $G$;
the ...
4
votes
1
answer
2k
views
Probability of two vertices being connected in a random graph
Consider a random directed graph with $N$ vertices where each vertex $v$ has exactly one link to some vertex (maybe to itself) $u$ with known probability $a_{vu}$. What is the probability of ...
4
votes
1
answer
1k
views
Graph where non-adjacent vertices share a common neighbor?
Suppose $B$ is a bipartite graph on $n$ vertices with minimum degree $\delta$. It can be shown fairly easily that if $4 \delta >n$, we have the nice property that any two vertices in the same ...
4
votes
1
answer
263
views
Alternative proof for counting problem in graphs
Let $G$ and $H$ be graphs, let $\vec H$ be a fixed orientation of $H$.
Denote by $D(G,\vec H)$ the number of orientations of $G$ that contain a copy of $\vec H$ and denote by $D'(G,H)$ the number of ...
4
votes
1
answer
278
views
If a graph invariant is NP-Hard, is its "deck ratio" NP-Hard as well?
This question is inspired by the Graph Reconstruction Conjecture. Suppose that $\psi$ is some graph invariant and that it is NP-Hard. There is a plethora of examples, of course. Now define $D_{\psi}(G)...
4
votes
1
answer
222
views
Existence of (Cut-Based) pseudorandom graphs beating the random graph
The question is simply this: Does there exist a (family of) graph $G=(V,E)$ such that $\max_{S\subset V} |E(S,S^c)- \frac{|S||S^C|}{2}|\leq o(n^{3/2})$. Such graphs would be very pseudorandom as the ...
4
votes
1
answer
251
views
An optimization involving (random) graphs
Suppose we have a graph on $n$ nodes. We would like to assign to each node either a $+1$ or a $-1$. Call this a configuration $\sigma \in \{+1,-1\}^n$. The number of $+1$s that we have to assign is ...
4
votes
1
answer
964
views
Algebraic structure generated by primitive graph operations
Let $M$ be a finite set, and
$S(M) = \{(f_0, f_1) | f_0, f_1: M → M\}$.
Each element of $S(M)$ can be considered as a finite directed graph with the set of nodes $M$, which has exactly two arrows ...
4
votes
1
answer
1k
views
Simplest examples of unique-solution and unsolvable-without-backtracking Sudoku-like problems
A
The Sudoku game admits a broad generalization as follows : let $r$ be an integer $\geq 2$
and let $X$ be a finite set, and ${\cal X}$ be a collection of $r$-subsets of $X$
(i.e, a $r$-uniform ...
4
votes
1
answer
727
views
In search for isotropic graphs: Straight lines and parallels
I wonder why I can find only so little attempts of concisely defining "directions" and "isotropy" of graphs.
In Euclidean spaces "directions" can be identified with ...
4
votes
1
answer
349
views
Ramsey pairs of classes graphs
Motivation
Call a set $H$ of vertices of a graph $G$ homogeneous if it is either independent or complete.
Every perfect graph of size $n$ has a homogeneous subset of size $\sqrt n$.
Noga Alon has ...
4
votes
1
answer
230
views
Negative Association of Component Size in Random Hypergraph
I have a $d$-uniform hypergraph on $n$ vertices with $k$ hyperedges, where $d << k$ and $n = 4k d^2$ or so.
The hyperedges are placed independently uniformly at random. I would like to have a ...
4
votes
1
answer
534
views
Diagonally-cyclic Steiner Latin squares
A Steiner triple system is a decomposition of $K_n$ into $K_3$, such as $S=\{013,026,045,124,156,235,346\}$. Steiner triple systems give rise to a Steiner Latin squares, such as $L$ below.
\[L=\left(...
4
votes
0
answers
214
views
Optimal colorings
If $G=(V,E)$ is a graph, we call the smallest cardinal $\kappa$ such that there is a coloring map $c:V\to \kappa$ as the chromatic number of $G$ and denote it by $\chi(G)$.
For any coloring $c:V(G) \...
4
votes
0
answers
126
views
"Neighborhood-Bounded" regular graphs
Lately I have been interested in questions surrounding strongly regular graphs, and came across this question that I have been struggling to make progress on. (For the sake of being explicit, a graph $...