Questions tagged [graph-theory]

Graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects.

Filter by
Sorted by
Tagged with
4
votes
1answer
129 views

Properties of toroidal graph

I am interested in work pertaining to graphs that have genus 1 i.e. toroidal graphs. Specifically, i am trying to find answers to the questions below. Since toroidal graphs can be recognized in $P$ , ...
1
vote
1answer
533 views

Common terminology used for lower/upper bounds

Suppose you have developed an upper bound on the number of vertices of a particular graph. This bound is the best possible bound that can be found for any given instance. What do you call such a bound?...
7
votes
3answers
1k views

What are graph grammars?

I have found information on graph grammars and graph rewriting, but the papers that I find on it are a bit thick. Can someone give a quick overview of what graph grammars are, as well as an overview ...
12
votes
1answer
233 views

For any two non-isomorphic graphs $G, H$, does there exist a polysize, polylog quantifier depth first order formula which witnesses this?

I want to be very specific. Does anyone know of a disproof or a proof of the following proposition: $\exists p \in \mathbb{Z}[x], n, k, C \in \mathbb{N},$ $\forall G, H \in STRUC[\Sigma_{graph}] (...
4
votes
0answers
128 views

Girth of graphs that decompose into two disjoint union of spanning trees

Let $G$ be an $n$-node graph that can be decomposed into two disjoint union of spanning trees. In particular, $G$ has $2n-2$ edges. It is not hard to show that the girth of $G$ is at most $O(\log n)...
7
votes
1answer
164 views

Complexity of finding semi-ordered Eulerian tours in a 4-regular graph

I'm trying to figure out the time-complexity of the problem I describe below, which I call the semi-ordered Eulerian tour problem or the SOET problem. Either finding an efficient algorithm for this ...
2
votes
2answers
231 views

One Generalization of Graph Isomorphism Problem

Say I generalize the language which consists of pairs of isomorphic graphs to take the following form: $GI(f) = \{ (G, H) \mid \exists \psi : V_G \rightarrow V_H, Pr_{a, b \in V_G} ((a, b) \in E_G \...
-2
votes
1answer
84 views

Algorithm finding path with maximal ratio of white vertices [closed]

Recently I encountered an interesting graph problem and couldn't find proper solution: given undirected graph G = <V, E>, each vertex is either white or black....
4
votes
1answer
120 views

Minor and subdivision

It is a well known fact that if $H$ is a graph of maximum degree 3, then $H$ is a minor of a graph $G$ if and only if $H$ is a topological minor of $G$. Moreover, a graph $G$ has one of $K_{3,3}$ or $...
5
votes
0answers
127 views

Graceful labeling completion problems

A graceful labeling of a graph with $m$ edges is a labeling of its vertices with some subset of the integers between $0$ and $m$ inclusive, such that no two vertices share a label, and such that each ...
8
votes
1answer
209 views

Decomposition of edges of eulerian graph into maximum number of cycles

I'm interested in the following problem. Given an eulerian graph $G=(V,E)$, we are to find a partition of its edges $C_1, C_2, \ldots, C_k$ ($\cup_i C_i=E$ and $i \neq j \leftrightarrow C_i \cap C_j =...
1
vote
1answer
108 views

Complexity of listing all minimal cut sets / connected 2-partitions of a graph

I am trying to find an algorithm that would give me for a given graph all minimal cut sets or equivalently all ways to partition the graph in two connected components. I am searching for an algorithm ...
4
votes
0answers
746 views

Optimizing Maximum Weighted Matching (Edmonds Blossom)

Background: I've ported Edmonds Blossom Algorithm with Maximum Weighted Matching to Java: https://github.com/simlu/EdmondsBlossom/blob/master/src/Blossom.java The original Python implementation ...
2
votes
0answers
65 views

Complexity consequence of logarithmic boolean width of co-bounded degree graphs?

The paper On graph classes with logarithmic boolean-width claims that the boolean width of co-k-degenerate graphs is at most $k\log{n}$ and a lot of graph vertex partition problems can be solved in ...
6
votes
0answers
129 views

Book/ Monograph on graph minor theory [Reference request]

I want to learn graph minor theory. Now i have read the very basic things and the overview from the book of R.Diestel but proceeding further is getting difficult. Currently, I am also following the ...
2
votes
0answers
65 views

The algebraic connectivity of graphs with large isoperimetric number

I asked this question on MO, but no answer. Let $G = (V,E)$ be an undirected graph with maximum degree $\Delta$. the isoperimetric number of $G$, denoted $i(G)$, is defined by $$i(G) = \min_{|S| \leq |...
6
votes
1answer
124 views

Directed graph with bounded in-deg can be partitioned in a balanced way

I want to prove that for all $n$, there exists a constant $c(n)$ such that if $G=(V,E)$ is a directed graph with in-degree bounded by $n$, it is possible to partition the set of vertices $V$ into two ...
4
votes
1answer
1k views

Minimal Cost of Eulerian Path

Problem: Given a planar (undirected and mostly sparse) graph with an Eulerian Path, we introduce a cost function f: (v, e1, e2) for all two edges e1 and e2 that share a vertex v. The function also ...
2
votes
1answer
71 views

Almost regular subhypergraph of hypergraph with large minimal degree

I am interested in knowing whether the following conjecture is true or not: For every $d \geq 1$ there exist constants $\delta,M_0 > 0$ such that the following holds for all $M \geq M_0$. ...
4
votes
1answer
349 views

Modifying Edmonds' Blossom Algorithm

Given a connected road network on an Island without one-way streets, where should I para-shoot in and what route should I take to deliver mail to all houses on the island (being picked up again by ...
1
vote
1answer
541 views

Clique cover problem

Consider the following graph problem. We are given a graph $\mathcal{G} = (\mathcal{V},\mathcal{E})$, where $\mathcal{V}$ is the set of vertices and $\mathcal{E}$ is the set of edges. For each vertex $...
0
votes
1answer
111 views

What is known about counting bipartite perfect matching with average degree in $[2,3]$ and max degree $3$?

We know counting perfect matching for bipartite graphs with vertex degree $2$ is in $P$ while counting perfect matching for graphs with vertex degree $3$ is in $\#P$. We also know there are degree $3$...
3
votes
1answer
226 views

Existence of $d$-regular expander graph that can be represented as a bipartite graph

It is easy to derive from the definition of expander graphs that a $n$-vertex expander graph $G$ does not have a $o(n)$-vertex/edge separator. I was wondering if we can build a $d$-regular expander ...
5
votes
0answers
156 views

reference clarification: Whitney's theorem on unique embeddability of 3-connected planar graphs?

This is a question about the correct reference for a result that seems to appear frequently in the literature on planar graph isomorphism. In "A $V \log V$ Algorithm for Isomorphism of Triconnected ...
2
votes
1answer
93 views

Counting xyz-graphs in $\mathbb{Z}_n^3$

This is a followup question to: Lower bound on the largest restrained cubic subset How many distinct xyz-graphs exist in $\mathbb{Z}_n^3$? We denote this number as $C(n)$ This question may be seen ...
3
votes
2answers
126 views

Lower bound on the largest restrained cubic subset

Consider an $n \times n \times n$ cube. I would like to consider subsets of points in the cube with the two following constraints: Each row in the cube (in any of the three directions) has exactly 2 ...
6
votes
1answer
180 views

Graph rewriting with one-to-many pattern matching?

In the single-pushout approach to graph rewriting, many nodes in a pattern graph can be matched to a single node of a target graph. My question is if there is a notion of graph rewriting where the ...
-1
votes
1answer
132 views

A conceptual question regarding hardness proofs by reduction [closed]

If we restrict the input domain of a known NP-hard problem P so that this restricted domain is equal to the input domain of another problem S, then show that we can reduce a solution to P given input ...
2
votes
0answers
81 views

Graphs for which the number of shortest paths between every pair of vertices is polynomially bounded

Let $G$ be a graph with $n$ vertices and $m$ edges, such that for every two vertices $u$ and $v$, the number of shortest paths from $u$ to $v$ is bounded by some polynomial $poly(n,m)$ in $n$ and $m$. ...
3
votes
2answers
448 views

Is this vertex ordering optimization NP-Hard?

Could you help me to prove that the following problem is NP-hard? Problem. Given an undirected graph $G=(V,E)$, find an ordering of the nodes such that $\sum\limits_{v\in V}|succ(v)|\times|pred(v)|$ ...
1
vote
0answers
73 views

limit the total flow for some edges in an directed graph

How can I limit the total flow for some edges in an directed graph. We know that every edge can have an upper and lower bound solely. But apart from this sole upper and lower bounds for each edge, if ...
3
votes
1answer
121 views

Hadwiger number under matching contraction

Given a graph $G$ with Hadwiger number $h(G)$ and a matching $M$ of $G$. Let $G/M$ be the simple graph obtained by contracting $M$. I am looking for a lower bound on the Hadwiger number of $G/M$ as a ...
0
votes
1answer
98 views

Reachability in Dynamic Line Graph

Given a directed line graph $G = v_1 \rightarrow v_2 \rightarrow \cdots \rightarrow v_n$, there are two operators, namely $\mathsf{move}(v_i, v_j)$: this operator moves $v_i$ to the position ...
2
votes
2answers
76 views

Maximal non-reducible vertex cover of a graph

Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph). We say that a vertex cover $V'$ of $G$ is non-reducible if any $V''$ with $V''\subsetneq V'$ is not a vertex cover of $G$. We say ...
0
votes
0answers
103 views

Path-width and chromatic number

How would I prove that the chromatic number of a graph $G$ is smaller than or equal to the path-width of $G$ + 1? or $\chi(G) \leq pw(G) + 1$
-1
votes
1answer
169 views

Is there a name for graph regions that lie between two nodes?

Perhaps a bit more formally, is there a name for regions delimited by nodes A and B, in a directed graph, where all paths starting from A, when prolonged, will eventually reach B, and all paths ...
0
votes
1answer
55 views

How to check whether graph of n vertex contains n/k disjoint k - complete graph by linear programming? [closed]

Edges are given in form of $X_{ij}$, which denotes whether there is edge in between $i^{th}$ and $j^{th}$ vertex. I am solving integer optimization problem and want to add this constraint to it.
1
vote
0answers
258 views

Can Lexicographic BFS be implemented in logspace?

Input: Given graph $G=(V,E)$ vertex labeling in some order Output: Change the labeling of vertices's such that labeling start $v_1$ as $u_1$, next label the neighbors of $v_1$ as $u_2,u_3,u_4,...$ ...
7
votes
2answers
264 views

What is the connection between moments of Gaussians and perfect matchings of graphs?

Today, I heard the following statement in a talk: The 4th moment of a $1$-dimensional Gaussian distribution with mean $0$ and variance $1$ is the same as the number of perfect matchings of a ...
7
votes
1answer
175 views

Automata : Language Containment, Minimality & Graph Homomorphism

Given two DFAs $A$ and $B$ defined on the same alphabet, a (graph) homomorphism $h:A \rightarrow B$ from $A$ to $B$ is a mapping of the states of $A$ into the states of $B$ such that : if the state $...
5
votes
2answers
233 views

Log space algorithms for modular decomposition tree

Can we have log space algorithms for modular decomposition tree (see definition) for any graph? If not, can we have log space algorithms for modular decomposition tree for any particular graph class? ...
5
votes
0answers
96 views

Optimal polynomial time algorithm to determine if a random graph is $k$-colorable

Let $G(n, d/n)$ be an Erdos-Renyi graph with edge probablity $p = d/n$. For any fixed $k$ sufficiently large, it is known that $d_{k-col} \sim 2 k\log k$ is the sharp threshold for $G(n, d/n)$ to be $...
8
votes
1answer
230 views

Vertex isoperimetric number of a graph - NP-hard?

The vertex isoperimetric number of a graph $G=(V,E)$ is $i_V(G) = \min\{\frac{|N(S)|}{|S|} : S \subseteq V, 1\le |S|\le \frac{|V|}{2}\}$. Several academic papers state that the problem of computing ...
1
vote
0answers
99 views

Non-backtracking paths and the zeta function of graphs

This question has also been posted on mathSE here: https://math.stackexchange.com/questions/2215888/non-backtracking-paths-and-the-ihara-zeta-function For a connected $d$-regular graph $G=(V,E)$ with ...
3
votes
2answers
528 views

A generalization of edge cover

Suppose we are given a general (connected) undirected graph $G = (V, E)$. An EDGE COVER asks a set $S\subseteq E$ of the minimum number of edges, such that each vertex $v\in V$ is incident to at least ...
14
votes
2answers
529 views

Add a matching to a Hamiltonian path to reduce the max distance between given pairs of vertices

What is the complexity of the following problem? Input: $H$ a Hamiltonian path in $K_n$ $R \subseteq [n]^2$ a subset of pairs of vertices a positive integer $k$ Query: is there a matching $M$ such ...
8
votes
0answers
271 views

Embedding a graph with specified edge lengths in d-dimensional space

Given any undirected edge-weighted graph (with weights > 0) and some dimension d, is there a way to assign positions in $\mathbb{R}^d$ to those vertices such that all of the edges between them have ...
1
vote
1answer
139 views

Number of solutions to the biclique cover problem

Given a bipartite graph and the number bicliques K, how many ways exist to solve the biclique cover problem using K (possibly empty) bicliques?
13
votes
1answer
565 views

Are there interesting graph classes where the treewidth is hard (easy) to compute?

Treewith is an important graph parameter that indicates how close a graph is from being a tree (although not in a strict topological sense). It is well known that computing the treewidth is NP-hard. ...
0
votes
1answer
667 views

What is “Synthetic Network” in Network Science?

I checked out several articles, books available, but didn't find what exactly is a "synthetic network".