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

0
votes
0answers
10 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 ...
-3
votes
0answers
36 views

Can any polynomial expressed as a chromatic polynomial?

Is it possible any polynomial with integer coefficients to be (or converted to) a chromatic polynomial that corresponds to a graph?
6
votes
2answers
307 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 ...
0
votes
0answers
41 views

Finding isomorphism that is labelled differently for non-Symmetric matrices (Bi-partite graph)

Summary: It is given that all isomorphisms are labelled two different ways in two different permutation sets for a pair of bipartite graph/ non symmetric matrices. How can we find a particular ...
11
votes
1answer
951 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 ...
4
votes
3answers
167 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
13 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
452 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
50 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
179 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
34 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$ ...
-3
votes
0answers
36 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
31 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
53 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
47 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
244 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
544 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
228 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
592 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
30 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
43 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
132 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
54 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
171 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 ...
2
votes
1answer
91 views

A centralised website for computational attempts in graph theory and metric geometry?

The set of questions below stems from this question. 1) does a website exist that contains (at least links to) code and data files, with the aim to centralise computational results in graph ...
5
votes
1answer
218 views

Graph spectra and topology

This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph. To give an ...
6
votes
1answer
126 views

Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...
2
votes
1answer
99 views

What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices. Analogously, what is the ...