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

learn more… | top users | synonyms (1)

3
votes
0answers
94 views

NP-hardness of tasks graph assignment to two heterogenous servers

I have a problem with determinig if the following assignment problem is NP-hard. Any comments and suggestions would be appreciated. Problem definition Given is a directed acyclic graph $G=(V,E)$ ...
-3
votes
0answers
24 views

Tree Traversal - Simple Puzzle type Issue

This is a puzzle like question,based on Fibonacci like structure of the tree. Actually it is a short question with out any complex concepts. It appears bit big,since I have added explanations with ...
1
vote
1answer
178 views

Is there simple reduction Dominating Set to Vertex Cover?

Is there simple reduction Dominating Set to Vertex Cover? In the other direction the reduction is simple. Searching the web returned blog. It warns This is not finished yet and experiments ...
0
votes
0answers
30 views

Estimating Graph/ Network Accuracy

If I'm creating a (social) network using some automatic system, which I know is not 100% accurate but for which I can estimate the rate of error, what, if anything, can I say about the accuracy of the ...
0
votes
1answer
62 views

What is a minimum vertex separator as in this definition?

In a research paper the following definition appears that I'm not able to understand completely. Let $G=(V,E)$ be an undirected unweighted graph with vertex set $V$ and edge set $E$, no self-loops, ...
1
vote
0answers
91 views

Complexity of an algorithm for deciding 3-colorability of graph by the chromatic polynomial modulo $x-3$

As explained on MO computing the chromatic polynomial $P(G,x)$ modulo $x-3$ is enough for deciding 3-colorability. For non adjacent vertices $u$ and $v$, $G+uv$ is the graph with the edge $uv$ added ...
0
votes
1answer
43 views

References to learn more about graph laplacian.

I have vaguely heard of this connection between random matrix theory and graphs (the spectral gap of their laplacians) on compact Riemann surfaces. Can someone give a pedagogic reference which ...
5
votes
0answers
60 views

Sparse subgraph preserving rooted edge connectivity up to $k$

For a graph $G=(V,E)$ with $n$ vertices and $m$ edges, a subgraph of $O(kn)$ edges is an $r$-rooted-$k$-sparsifier if it preserves the local edge connectivity from $r$ to every other vertex up to ...
2
votes
0answers
53 views

Weighted graph as average of many unweighted graphs

I have a measure $L(G)$ that is only valid for unweighted graphs because is based on discrete distributions and can't be extended to weighted graphs. My idea is that if I consider a weighted graph as ...
2
votes
1answer
209 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is $NPI$ candidate). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ pairs of nodes $(u, v)$ where $u ...
3
votes
1answer
77 views

any relation/ overlap between small world graphs, scale free graphs, and expander graphs?

small world graphs (eg Watts-Strogatz model & others) and scale free graphs are a relatively recently discovered graph type via mainly empirical analysis of large real-world graphs (eg via Big ...
-1
votes
0answers
39 views

Maximal-clique to domination number

Suppose for a graph family, i have an algorithm to compute all the maximal cliques in polynomial time. Is it possible to compute the Dominating set in polynomial time? So far, i have tried to use the ...
-4
votes
0answers
82 views

Preserving connectivity from a vertex by edges deletion [migrated]

Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all ...
3
votes
0answers
43 views

Interpolating the Tutte polynomial at the values of two hyperbolas

In a MO question basically I asked when the Tutte polynomial of planar graph can be uniquely determined by the polynomially computable values at the special points and at the two hyperbolas. The ...
4
votes
1answer
46 views

Bipartite scale-free networks

The Barabasi-Albert model describes a mechanism of generating random scale-free networks: Growth: Starting with a small number ($m_0$) of connected nodes, at every time step, we add a new node with ...
3
votes
0answers
40 views

Bipartite small-world networks

The Watts-Strogatz model describes a mechanism of generating small-world networks. The idea is to start from a ring network in which each node is connected a fixed number of its closest neighbors. ...
2
votes
0answers
40 views

Linear ordering of bipartite tournament graphs

I have an ordered bipartite graph such that every node of the first node set is connected to every node in the second node set by an edge of a given direction (i.e., a so-called bipartite tournament ...
0
votes
0answers
74 views

Regularlity lemma and exceptional set

Regularity lemma is one of the most basic tools in algorithmic thoery and pure math theory like additive number theory and combinatorics. This lemma is stated two ways: the existence of a partion ...
4
votes
0answers
62 views

Spectrum of absorbing random walk for regular graphs

I have a symmetric Markov chain given by the matrix $P$. Let $M$ be a set of special states of the chain (called marked states, they correspond to solutions to some problem). We can write $P$ as ...
15
votes
0answers
138 views

Mixing properties of random walks on graphs

I have a question about this paper (not behind a pay wall) on the Cheeger inequality for graphs. One of the main ideas of the paper is that random walks on graphs can be used to find sets with small ...
6
votes
0answers
92 views

Confusion about reduction counting vertex covers to counting cycle covers

This confuses me. One easy case of counting is when the decision problem is in $P$ and there are no solutions. A lecture show that the problem of counting the number of perfect matchings in a ...
9
votes
1answer
220 views

Hidden path in square grids

I stumbled on an open problem posed by David Eppstein and I am interested in its complexity status. He conjectured that it is NP-complete. Input: $n$ by $n$ matrix of 0’s and 1’s, sequence of $n^2$ ...
0
votes
1answer
157 views

Proving properties of Random Graphs

I am asking the question on a slightly abstract level and it may depend on the specifics but it would be great to have related references or ideas. Consider the random graph model $G_{n,p}$ where its ...
2
votes
0answers
79 views

What is the name for this special case of the Travelling Salesman involving dynamic edge costs?

This is a modeling / taxonomy question. Is there a name for this type of problem? I came up with the following graph problem for a pizza delivery truck, which starts with zero dollars and enough fuel ...
2
votes
1answer
106 views

When replacing an edge with a graph gadget preserves graph isomorphism?

The transformation replacing an edge by a graph gadget is widely used in graph theory. As an example, in an answer Marzio De Biasi subdivided edges which increases the girth while preserving GI. A ...
-1
votes
1answer
97 views

What can we say about all cycles in graphs (connected undirected graph)

I am considering one optimization problem who is known to be NP hard in the general setting. But there is application of this problem on the cylces of graph. This problem involves several sets and ...
4
votes
0answers
109 views

Complexity of edge coloring graphs with $\Delta(G) \ge n/3$

Let $C$ be the class of graphs satisfying $\Delta(G) \ge n/3$, where $\Delta(G)$ is the maximum degree of a graph $G$, and $n$ denotes the number of vertices. What is the complexity of edge coloring ...
5
votes
1answer
147 views

The Overfull conjecture in graph theory and $coNP$

I am not good at complexity, but got a possible relation between a plausible conjecture in graph theory and $coNP$. Graph $G$ is Class 1 if it can be edge colored with $\Delta(G)$ colors, otherwise ...
2
votes
1answer
83 views

For which graph classes the fractional chromatic index rounded up equals the chromatic index?

Let $\chi'_f(G)$ be the fractional chromatic index. For which graph classes $\lceil \chi'_f(G) \rceil = \chi'(G)$? Since $\chi'_f(G)$ is computable in polynomial time, solving this gives tractable ...
6
votes
0answers
76 views

Hard extendability problems

In extendability problem, we are given part of the solution and we want to decide whether we can extend it to a complete solution. Some extendability problems are efficiently solvable while other ...
1
vote
0answers
36 views

Maximal Unit interval graph construction

Is it possible to construct a unit interval graph with $n$ vertices and clique number $k$ such that any other unit interval graph with same number of vertices and clique number is a sub-graph of that ...
0
votes
1answer
122 views

Does this paper imply graph isomorphism is polynomial for cubic and $4$-regular graphs?

This paper gives example of polynomial GI for certain graphs. Probably I am misunderstanding the paper, but appears to me it implies polynomial GI for cubic, $4$-regular and probably higher degree ...
7
votes
4answers
448 views

Polynomial problems in graph classes defined by forbidden induced cyclic subgraphs

Crossposted from MO. Let $C$ be a graph class defined by a finite number of forbidden induced subgraphs, all of which are cyclic (contain at least one cycle). Are there NP-hard graph problems ...
4
votes
1answer
128 views

$\ell_1$ norm of Fourier coefficients vector for the hypercube

Let $G$ be the normzlied hypercube graph on $2^d$. It is a Cayley graph and it is well known that its eigenvalues are given by $\lambda_r = 1-2\frac{|r|}{d}$ for every $r \in \{0,1\}^d$. Given a ...
1
vote
0answers
39 views

Minimum Clique edge cover to cilque vertex cover

Suppose, there is an algorithm for enumerating minimum clique edge cover. Is it always possible to convert the algorithm to enumerate clique vertex cover ?
2
votes
1answer
53 views

Infinitary Counting Logics: 1-sorted vs. 2-sorted framework

There are two ways to extend infinitary logic with counting: Grädel's way (cf. p. 11): We extend $L_{\infty\omega}$ by introducing a counting existential quantifier: $$ \mathcal{A} \models ...
-4
votes
1answer
119 views

Destroy shortest path in graph

Given graph G(V,E)and two vertices A and B, show how to eliminate the least number of edges so that length of shortest path between A and B become longer.(I need an algorithm)
2
votes
2answers
119 views

An upper bound over the number of bipolar orientations for a regular graph

Given a $k$-regular graph $G$, the number of acyclic orientations $Acy(G)$ is $\chi(-1)$ where $\chi$ is the chromatic polynomial of $G$. How many bipolar orientations does $G$ have? Is there an ...
0
votes
0answers
67 views

planted cliques in continuous graphs?

The question is pretty simple (almost the same as that mentioned in the title). Is there an equivalent definition of the planted clique problem for Continuous graphs ...
0
votes
0answers
99 views

Distance oracles in trees

Given an unweighted tree $T=(V,E)$ what is the minimum number of distance oracles that allow to detect the position in the graph of every node $v$? A distance oracle is "special node" $u$ of the ...
2
votes
0answers
133 views

Independent Sets that are Odd Covers

I am interested in a certain type of independent set I call an "odd cover". A set of vertices is independent if no two vertices in the set are connected with an edge. A set of vertices is an "odd ...
3
votes
0answers
136 views

Standard reference for efficient computation of non-intersecting Eulerian circuit

A plane graph $G$ defines a cyclic ordering $O(v) = \langle v_1, v_2, \dotsc, n_{\deg(v)}\rangle$ on the neighborhood $N(v)$ of each vertex $v \in V(G)$. A non-intersecting Eulerian circuit $C$ is an ...
4
votes
1answer
159 views

Relation between tree-width and clique number

Are there any nice graph classes for which the tree-width $tw(G)$ is upper-bounded by a function of the clique number $\omega(G)$, i.e. $tw(G)\leq f(\omega(G))$? For example, it is a classic fact ...
8
votes
2answers
206 views

For which families of graphs is Generalized Geography in $P$?

As @Marzio mentioned, the following game is known as Generalized Geography. Given a graph $G=(V,E)$ and a starting vertex $v \in V$, the game is defined as follows: At each turn (two players ...
6
votes
2answers
346 views

What is the probability of a virus spreading through a network given a virus source node?

Model: Consider an infinite undirected connected graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$. At time $t=0$, a given virus node $s\in\mathcal{V}$ starts infecting the network $\mathcal{G}$. ...
10
votes
0answers
196 views

A bijection between ordered lambda terms and rooted planar maps?

Consider the following recurrence in two parameters $n$ and $k$: \begin{aligned} NF(0,k) &= 0 \\ NF(n,k) &= Neu(n,k) + NF(n-1,k+1) \\ Neu(n,k) &= [n=1 \wedge k=1] + ...
3
votes
0answers
92 views

Bound on a graph diameter, considering the minimal vertex degree

Let $G$ be a connected (strongly connected) graph (digraph). Assume that the minimal vertex degree (in/out degrees) of the graph is $\delta$ (are $\delta^-,\delta^+$). What is the maximal diameter ...
0
votes
0answers
43 views

Competitive throughput model definition

I am reading a paper on optimal node routing and it is mentioning the phrase "competitive throughput model". I have searched for a definition, but I didn't find anything. Could anybody give me a ...
19
votes
2answers
372 views

Is it necessary to call matrix multiplication $n$ times to find a claw

A claw is a $K_{1,3}$. A trivial algorithm will detect a claw in $O(n^4)$ time. It can be done in $O(n^{\omega+1})$, where $\omega$ is the exponent of fast matrix multiplication, as follows: take the ...
3
votes
0answers
128 views

Is there any equivalent for Bondy-Chvátal theorem for directed graphs?

Bondy-Chvátal theorem cannot be applied for directed graphs, is there any equivalent theorem that can be applied for them?