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
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 (...
ts09's user avatar
  • 41
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$ ...
Oliver's user avatar
  • 65
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 ...
Dmytro Korduban's user avatar
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 ...
David Harris's user avatar
  • 3,397
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 ...
Daniel Liu's user avatar
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 ...
Wolfgang's user avatar
  • 13.2k
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 ...
L.C. Zhang's user avatar
  • 1,605
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)...
Tri's user avatar
  • 1,366
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$...
Sidhanth Mohanty's user avatar
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 ...
L.C. Zhang's user avatar
  • 1,605
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 ...
Manfred Weis's user avatar
  • 12.6k
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, ...
Andi Bauer's user avatar
  • 2,901
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 ...
Ilya's user avatar
  • 251
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 $...
Will's user avatar
  • 105
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 ...
Lluís Alemany-Puig's user avatar
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 ...
Aidan Rocke's user avatar
  • 3,827
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 ...
Kcafe's user avatar
  • 509
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 ...
EGME's user avatar
  • 1,008
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 ...
vidyarthi's user avatar
  • 2,007
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 $\...
Alessandro Vignati's user avatar
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 ...
co.sine's user avatar
  • 403
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} & ...
Yonathan B.'s user avatar
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$, ...
Daniel Soudry's user avatar
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^...
D. Ror.'s user avatar
  • 399
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$...
Quentin Fortier's user avatar
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 ...
Igor Makhlin's user avatar
  • 3,493
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 ...
Maryam's user avatar
  • 147
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 ...
Kostub Deshmukh's user avatar
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 \...
Marek Adamczyk's user avatar
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 ...
Student's user avatar
  • 555
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, ...
user avatar
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 ...
Peter Dukes's user avatar
  • 1,071
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 ...
rwolst's user avatar
  • 141
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-...
Anon's user avatar
  • 41
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 ...
user40096's user avatar
  • 421
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 ...
sbos's user avatar
  • 219
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 ...
Anand's user avatar
  • 41
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 ...
László Kozma's user avatar
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)...
Felix Goldberg's user avatar
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 ...
Nick B.'s user avatar
  • 195
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 ...
passerby51's user avatar
  • 1,639
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 ...
Ewan Delanoy's user avatar
  • 3,565
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 ...
Hans-Peter Stricker's user avatar
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 ...
Stefan Geschke's user avatar
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 ...
Eric Price's user avatar
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(...
Douglas S. Stones's user avatar
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) \...
Dominic van der Zypen's user avatar
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 $...
Mary_Smith's user avatar

1
38 39
40
41 42
103