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, ...

learn more… | top users | synonyms

-1
votes
0answers
9 views

Expected number of tree component should be less than equal to zero in random graph

In Erdos-Renyi random graph $G(n,p(n))$, set $p(n) ≥ (\frac{\ln n}{10n})$. We want to show that expected number of tree component on 11 vertices with this probability $p(n) ≥ (\frac{\ln n}{10n})$ ...
15
votes
11answers
2k views

Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...
1
vote
1answer
70 views

Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$? I am most interested in $d\leq3$ and $g=0$.
0
votes
1answer
266 views

Reverse optimization of a minimum cost flow network

Given an undirected graph $(V,E)$, with $W$ as the weight of each edge, and a convex cost function $F(X)$, such as $|X|^k$ ($k>1$). The cost to send $x$ unit of flow through edge $e_i$ is defined ...
4
votes
3answers
175 views

Relation between diametral path and regularity of a graph

Let $G(V,E)$ be a graph. A path whose length is equal to the diameter of a graph is called a diametral path. In a cycle graph every vertex has $2$ diametral paths. Now I need to prove that this: ...
0
votes
0answers
44 views

Zero-one law in binomial random graph model $G(n,p)$

Consider the binomial random graph model $G(n,p)$ with $0<p<1$. We say that $G(n,p)$ satisfies the Zero-One law if for every first order property $Q$ one has $\lim\limits_{n \rightarrow \infty} ...
0
votes
0answers
35 views

Reconstructing a graph from set of sequences of edges

I have the following problem to solve: Given a set of sequences of edges of an undirected, planar, connected graph, find a "reasonable" reconstruction of the graph. There is an unknown number of ...
-5
votes
0answers
66 views

Can any polynomial expressed as a chromatic polynomial? [on hold]

Is it possible any polynomial with integer coefficients to be (or converted to) a chromatic polynomial that corresponds to a graph?
6
votes
2answers
316 views

Can every permutation group be realized as the automorphism group of a graph (acting on a subset of the vertices)?

By Frucht's theorem, every finite group can be realized as the automorphism group of a finite undirected graph. Because a permutation group is a finite group, it is clear that every permutation group ...
11
votes
1answer
952 views

Menger's theorem via matroids

Let $G=(V,E)$ be an oriented graph, $Y\subset V$ be some fixed set of its vertices. Call $A\subset V$ independent if there exist $|A|$ vertex-disjoint paths starting in $A$ and ending in $Y$. It is ...
0
votes
0answers
14 views

is any closed form relation that can state the error probability of code versus its variable and check node degree distributions?

In Low Density parity check code design, when bit (or frame) error probability of code is the objective of the design, we need a closed form relation between error probably (or even an approximate or ...
4
votes
1answer
454 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 ...
0
votes
0answers
51 views

Binary operations on graphs

Are there "binary operations" on graphs like in (https://en.wikipedia.org/wiki/Graph_product), which make the set of all graphs ("under consideration") a (abelian) group or a (commutative) ring or a ...
2
votes
3answers
182 views

Existence of special graph

Let $G$ be a $n$-vertices graph and $\lambda_1$ is the largest eigenvalue of this graph. If $\lambda_1$ is an integer value, we can easily find the $\lambda_1$- regular graph with $n$ vertices. Now, ...
0
votes
1answer
54 views

Choosing directed subgraph in a triangulation

Consider triangulation $T.$ Is it always possible to choose such a subgraph $H$ of $T$ that has a common edge with every face of $T$ and can be directed in such way that indegrees of all vertices of ...
0
votes
0answers
36 views

Limit probability of a complete bipartite random graph $G(n,n,p)$ is connected [on hold]

I need to calculate the following probability limit for a complete bipartite random graph $G(n,n,p)$ in the Erdos-Renyi model: \begin{equation} \lim_{n\rightarrow\infty}\mathbb{P}[G(n,n,p) \text{ is ...
1
vote
1answer
142 views

Finding many disjoint sub-trees with many leaves

Let $T$ be a rooted binary tree with $L$ leaves, and let $\ell$ be a natural number smaller than $L$. The question is what is the maximal number of disjoint rooted sub-trees with at least $\ell$ ...
-4
votes
0answers
37 views

Are Undirected Edges and Directed Edges disjoint sets? [closed]

Many graph processing and storage frameworks assume that, in their graphs, all edges are directed. There are no edge whose type is undirected under the hood. There is only an interpretation, when ...
2
votes
1answer
32 views

Edge-disjoint paths avoiding some subgraphs

Let $G$ be a directed graph on $n$ vertices. Let $H_1$, ..., $H_k$ be marked subgraphs of $G$. (Specifically, each $H_i$ consists of a subset of the vertices of $G$ and a subset of the edges of the ...
2
votes
0answers
54 views

Number of $(2n-1)$-edge-colorings of the complete graph $K_{2n}$

I just started reading about graph theory and have a question (which might be trivial). How many $(2n-1)$ edge colorings of $K_{2n}$ are there? A vaguer question: can I write $K_{4n}= K_4 + K_4 ...
-1
votes
0answers
49 views

Central limit theorem for perfect matching counts [closed]

This is a modification to one of my questions: Set $N_G$ the number of copies of graph $G$ in the Erdős–Rényi random graph model $G(n,p)$. We have the law of large number for the number of copies of ...
4
votes
2answers
245 views

Are all numbers from $1$ to $n!$ the number of perfect matchings of some bipartite graph?

Let $f(G)$ give the number of perfect matchings of a graph $G$. Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Consider collection of all $2n$ vertex balanced bipartite graph to be ...
0
votes
0answers
71 views

Understanding the significance of the values of an adjacency matrix [closed]

I am new to network/graph theory and I am trying to understand a few things. One of these is the significance of the i,j entry of an Adjacency Matrix. In an ...
0
votes
0answers
66 views

Missing count in number of perfect matchings

Let $f(G)$ give the number of perfect matchings of a graph $G$. Consider set $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$. Consider collection of all $2n$ vertex balanced bipartite graph to be ...
0
votes
1answer
254 views

Efficient isomorphic subgraph matching with similarity scores

I'm a computer vision PhD student, and I'm looking for an efficient approximation to the following problem, which could end up helping in image to image matching. Failing that, pointers to relevant ...
4
votes
1answer
66 views

Degree of neighbors in a simple graph (friendship paradox variant)

Context: this question is a translation of a common informal phrasing of the friendship paradox ("Most people have fewer friends than most of their friends"). Note that the question is similar to, but ...
3
votes
1answer
56 views

Maximal acyclic subgraph

It is well known that the problem of finding a maximal acyclic subgraph of a digraph is NP-complete. Is this the case also when the digraph is symmetric ,i.e. if $(a,b)$ is a link, then $(b,a)$ is ...
0
votes
0answers
11 views

Prove that the converse of a strong digraph is also strong [closed]

I would like to know how I prove this. The converse of a digraph D is obtained from D by reversing the direction of every arc of D. Show that a digraph D is strong if and only if its converse is ...
19
votes
3answers
548 views

Which paths in a graph are orthogonal to all cycles?

Start with some standard stuff. Suppose we have a directed graph $\Gamma$. I'll write $e : v \to w \,$ when $e$ is an edge going from the vertex $v$ to the vertex $w$. We get a vector space of ...
2
votes
0answers
48 views

Universal path function for all small trees

Let $f$ be a function $f: [k]^2 \rightarrow [k]$ (Where $[k]$ is the set $ \{0,1,\dots,k-1\}$). A function $f$ is called $n$-universal path function if for every tree $T$ with $n$ vertices there ...
0
votes
3answers
98 views

How to do a clockwise ordering of a planar graph in order to define its faces?

I am currently making an algorithm for planar graphs that I need to triangulate so they become maximally planar (that is triangulated and planar) given only the lists of neighbors for each node : no ...
1
vote
1answer
229 views

Hashimoto Matrix (Non-backtracking operator) and the Graph Laplacian

The question is: how can we recover the graph Laplacian or its spectrum from the Hashimoto Matrix (also commonly called the Non-backtracking operator)? To make the question as self-contained as ...
9
votes
2answers
596 views

Expected number of connected components in a random graph

For a random graph G(n,p) what is the expected number of connected components? What is the probability distribution of this value? I'm specially interested in what happens for small values of p, ...
2
votes
1answer
74 views

Do product distributions (or graph products) eventually cluster as more products are taken?

Say we have a joint distribution on a finite alphabet $\mathcal{X}\times \mathcal{Y}$. It could be a communication link where we want to send a random message $X$ over a channel, but it gets garbled ...
4
votes
1answer
204 views

minimal polynomial for a graph

I wonder if there is any result relating the degree $d$ of the minimal polynomial of a directed finite graph to any of its topological features - such as its diameter, or any other similar 'natural' ...
6
votes
1answer
434 views

How to find or constrain “particularly good” (two-sided) spectral expanders?

I'm new to graph theory, but a response to a question I asked a while ago introduced me to the concept of expander graphs. A k-regular graph (henceforth "graph") on n nodes has eigenvalues k = λ1 ≥ ...
4
votes
2answers
5k views

Reporting all faces in a planar graph

Hi, I was looking to traverse a planar graph and report all the faces in the graph (vertices in either clockwise or counterclockwise order). I have build a random planar graph generator that creates a ...
3
votes
2answers
133 views

Characterizing graphs whose Incidence Matrix has the all ones vector in its row span

Suppose we have a simple connected graph $G=(V,E)$. Then let $A$ be its $|E|\times |V|$ incidence matrix. Here I am considering the unoriented incidence matrix. I want to known when the row span of ...
3
votes
0answers
31 views

how to study the size of basins of attraction on a graph

I have a certain finite (but huge and without an apparent pattern, so that only numerical studies seem feasible) graph $G = (V,E)$, and a function $f: V \rightarrow \mathbb{R}$. On each edge $e = ...
4
votes
1answer
80 views

Choice number of embedded graphs

For given $g$, consider the family of graphs which may be embedded to the compact orientable surface of genus $g$. For this family, consider maximal clique $\alpha(g)$, maximal chromatic number ...
1
vote
0answers
55 views

bounded degree graph colouring.

I was wondering if anyone could provide references on the following: Is determining the chromatic number of a bounded degree graph APX-complete? 2.I've seen the result that states it is NP-hard ...
2
votes
0answers
45 views

Hypergraph edge colouring

I'm interested in knowing if finding the edge-chromatic number of a $k$-uniform $k$-partite hypergraph is NP-hard for $k\geq 3$ Could anyone provide a reference for the result? By edge-chromatic ...
2
votes
1answer
133 views

Product and coproduct for bipartite graphs

Consider the category $BiGraph$ of bipartite graphs (vertices are named "places" and "transitions" like in Petri nets) and continous maps. A subgraph is named open iff it is place-bordered, and a map ...
1
vote
1answer
89 views

Assigning random orientation to an edge in a regular graph

Given a simple regular graph of degree $d$ on $n$ vertices. Assume an ordering of vertices and assume all orientations of edges is from $i$ to $j$ if edges $ij$ exists and $i<j$. Pick $m$ random ...
19
votes
3answers
1k views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...
-3
votes
1answer
64 views

Connected homogeneous graphs [closed]

Let's call a simple, undirected graph $G=(V,E)$ homogeneous if for every $v,w\in V$ there is a graph isomorphism $\varphi:G\to G$ such that $\varphi(v)=w$. It is clear that every finite homogeneous ...
0
votes
1answer
55 views

Reference for Turan Density

I am working a 3-graph problem. I convert it to calculate Turan density, that is $lim_{n\to \infty}\frac{ex_3(n,F)}{\binom{n}{3}}$, where F is a3-graph. I'd like to know are there some methods and ...
14
votes
3answers
402 views

Spectral theory of graph Laplacian besides $\lambda_2$

Most of what I've seen about the spectral theory of the graph Laplacian concentrates on $\lambda_2$, the second-smallest eigenvalue. This eigenvalue contains information regarding the connectivity of ...
3
votes
1answer
173 views

A spectral graph theory problem

Let $S$ be a zero-free subset of the group ${\bf Z}_2^n$ and $\Gamma={\rm Cay}({\bf Z}_2^n,S)$ be a bipartite Cayley graph. For some choices of $S$, the graph $\Gamma$ has $4$ distinct eigenvalues, ...
4
votes
1answer
90 views

Behaviour of eigenspaces of adjacency matrices after a single change to the graph

Say I know the eigenvalues and eigenvectors of an adjacency matrix of an unweighted graph. Can I say anything about the eigenvalues and eigenvectors of an adjacency matrix of a graph with one extra ...