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

learn more… | top users | synonyms (1)

0
votes
1answer
37 views

Kuratowski's graph planarity criterion

There is a short proof of Kuratowski's graph planarity criterion. But I don't understand the proof, completely. So I hope someone may help me with that proof. Here is the short proof of Kuratowski. ...
5
votes
1answer
135 views

Independent set size of a large girth graphs

For triangle-free (girth $\geq 4$) graph $G$. The following theorem holds true Theorem (Ajtai et al.): For a triangle-free graph $G$ with maximum degree $\Delta$, $$\alpha(G) \geq ...
3
votes
0answers
112 views

#EXP-Complete problems

Let #EXP be the counting variant of NEXP, in the same way that #P is the counting variant of NP. Are there any known #EXP-complete problems? In particular, has #Succinct Sat (the natural candidate) ...
-2
votes
0answers
147 views

Is this notion of 'regular graph' known?

Let $S$ be a set, and consider a weighted digraph $D = (S,A,W)$ ($A$ a symmetric set and $W : A \rightarrow \mathbb{R}$ a weight function). Let $d$ be a positive real. By a $d$-potential for $D$, we ...
2
votes
1answer
72 views

Hardness of approximating chromatic number of triangle-free graphs

The chromatic number of graph, $\chi( G)$ is hard to approximate for general graphs. Are there results of hardness of approximating $\chi(G)$ for triangle-free graphs?
4
votes
1answer
76 views

Dual Barnette's Conjecture

Is every Eulerian triangulated (planar) graph Hamiltonian? On the other hand we have that: Barnette's Conjecture (Open): Every cubic bipartite (3-connected) planar graph is Hamiltonian. ...
-3
votes
0answers
87 views

Is finding the longest cycle in a directed graph vs undirected graph NP hard? [closed]

To find the girth or the shortest cycle in a directed/undirected graph one can for edge edge, remove it from the graph and find the shortest distance between the end points. The shortest such distance ...
-2
votes
0answers
28 views

Method to recognize abstract objects such as hand-drawn objects? [migrated]

My research is in the area of Document Image Analysis. To be specific, the topic of my thesis is to automatically recognize and index characters in a set of hand-drawn objects, e.g. given a volume of ...
0
votes
0answers
41 views

Representation of procedural knowledge

I know that knowledge about relationships between things can be represented using ontologies and stored in some sort of file or database system. Can a network of procedural knowledge also be created ...
2
votes
1answer
108 views

Dominating set problem

I am looking for websites or articles where can I find a data with test graphs for domination set problem. In my heuristic algorithms I use undirected and unweighted graphs. So I search for some ...
5
votes
0answers
102 views

Approximate c-chromatic number, each color class is P4-free (cograph)

The classic chromatic number of graph, $\chi(G)$, describes the minimum number of colors needed so that each color class is an independent set. There are many other graph coloring definitions. One of ...
24
votes
1answer
267 views

Can graph isomorphism be decided with square root bounded nondeterminism?

Bounded nondeterminism associates a function $g(n)$ with a class $C$ of languages accepted by resource-bounded deterministic Turing machines, to form a new class $g$-$C$. This class consists of those ...
7
votes
2answers
136 views

Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge. Note that the number of paths between two endpoints of a $k$-chain is $2^k.$ Question: Let ...
7
votes
0answers
79 views

Expansion of the union of two expander graphs

Suppose that $G$ and $H$ are both expander graphs on the same node set $V$ with a second largest eigenvalue of $\lambda_G$ resp. $\lambda_H$. Let $G\cup H$ be the graph on $V$ with the smallest set of ...
2
votes
1answer
78 views

Upperbound the order of P3-free partition of P4-free graphs

A graph $G$ is $P_k$-free if and only if $G$ does not have an induced subgraph isomorphic to a path of $k$ vertices. Thus, $P_2$-free graphs are exactly independent sets (or stable sets). $P_4$-free ...
0
votes
1answer
54 views

Number of $k$-cuts of grid graphs

Given a $n\times m$ grid, let the bottom-left vertex be $s$ and the top-right vertex be $t$. Given $k$ non-consecutive edges on the upper horizontal line of the grid, I want to find an upper bound on ...
0
votes
0answers
82 views

Help with a special case for Hungarian algorithm

I am working on a problem and it appears to be a special case of Hungarian algorithm. In Hungarian algorithm for assignment problem, there are n people and n jobs. Each person can do any of n jobs ...
5
votes
2answers
137 views

Subgraph of G whose maximum degree and minimum degree are of the same order

Consider a graph $G$ with max degree $\Delta_G$, min degree $\delta_G$ and average degree $d_G$. Is it possible to obtain a subgraph of $G$, say $G'$, such that $\Delta_{G'} = c_1d_{G}$, ...
1
vote
4answers
151 views

Turing-complete computation models on graphs

There are many Turing complete computation models and new ones are devised all the time. I am looking for Turing-complete computation models based on graphs?
-1
votes
0answers
35 views

minimum cut versus sparsest cut?

My question is that I'm trying to find the sparsest cut in a connected, undirected graph (all weights are = 1). Basically, I am looking trying to find the smallest cut (i.e., number of edges cut since ...
1
vote
1answer
76 views

Chordal Graphs and maximum independent sets

For a chordal graph $G$ there is a clique tree such that its vertices corresponds to maximal cliques of $G$ and there is a edge between two vertices iff the intersection of the corresponding cliques ...
1
vote
0answers
76 views

Chromatic number of a graph where neighbourhood of each vertex is isomorphic

Consider a graph $G(V,E)$. For any two vertices $v_1 , v_2 \in V$, the subgraph induced by the neigbourhood of vertex $v_1$, denoted by $G_{v_1}$ be isomorphic to the subgraph induced by the ...
0
votes
0answers
38 views

Are there any implementations of a graph crossing algorithm?

This is much more focused version of this question: Are there good implementations for easy subclasses of NP-hard graph problems Computing the graph-crossing number $cr(G)$ for a simple graph is ...
1
vote
0answers
82 views

Predicting the growth of a social network

I am building a predictive model for the growth of the amount of users of a new p2p protocol inspired by bitcoin and I would like to use historical data collected from the growth of major social ...
-1
votes
1answer
95 views

How to prove that a 3-connected 5-regular planar graph has chromatic number <= 4?

I can think of a way that to prove a 3-connected 5-regular planar graph does not contain a 5-critical subgraph. We can choose two non-adjacent vertices a,b and contract them into a single vertex. If ...
6
votes
2answers
651 views

Anti-chromatic number

What is the maximum number of colors that can be used for coloring the vertices of a given graph, with no isolated vertices, such that each vertex should share its color with at least one of its ...
3
votes
2answers
129 views

How many induced subgraphs does $G$ have of specific size

Let $G$ be a connected graph with $n$ vertices and $O(nk)$ edges, ($k$ is parameter). Then how many connected induced subgraphs of size $l$ does $G$ have? The simple case when $l=2$, The number ...
-5
votes
1answer
53 views

Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
10
votes
4answers
248 views

Which properties of planar graphs generalize to higher dimension / hypergraphs?

A planar graph is a graph which can be embedded in the plane, without having crossing edges. Let $G=(X,E)$ be a $k$-uniform-hypergraph, i.e. an hypergraph such that all its hyperedges have size k. ...
4
votes
1answer
87 views

Generalizations of planar graphs that include hypercubes with large side length in $R^d$

A lot of people have asked about generalizations of planar graphs on other forums. Some topics include: http://mathoverflow.net/questions/7650/generalizations-of-planar-graphs ...
-2
votes
0answers
66 views

How to assign unique ids to vertices in a graph deterministically?

Consider a directed graph G = (V,E). Each vertex has a name associated with it, which is a string of characters. However, the names are not unique in the graph. We would like to be able to uniquely ...
5
votes
1answer
101 views

Independent set size in triangle-free graphs

Consider a triangle-free graph $G$. The notations used are: $\alpha(G) = $ the size of a largest independent set of $G$. $n(G) = $ the number of vertices in $G$. Theorem (Ajtai et al.): For a ...
0
votes
0answers
128 views

A* in triangulated search space

I have a question regarding the optimality of a specific A* in triangulated search spaces (planar). Suppose I have some convex polygon (the boundary) with some number of obstacles (other convex ...
7
votes
3answers
160 views

On the size of P4-transversals of graphs

A subset $T$ of vertices of a graph $G$ is called a $P_4$-transversal if $T$ intersects every $P_4$ of $G$. In the context of this question, we consider $P_4$ as an induced path on 4 vertices. ...
2
votes
1answer
69 views

Fast approximation of (vertex) clique cover

I'm looking for a fast algorithm to find a clique cover on an undirected unweighted graph. I'm not looking for an optimal solution (ie minimal number of cliques). Obviously I'm also not looking for a ...
1
vote
1answer
63 views

What graph properties only consider neighbours of a node in their calculations?

I'm looking for graph properties which only consider neighbours of a node and do not go beyond that. For example, nodes degree only considers neighbours or clustering coefficient also consider only ...
0
votes
1answer
79 views

Comparing two graphs

I have a quite big graph which has millions of nodes and edges. I modify the graph using an algorithm which only changes small portion of edges. At then end, I'd like to investigate how the algorithm ...
2
votes
1answer
144 views

Extensions of Matrix-Tree Theorem

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) ...
1
vote
1answer
81 views

Finding a special cut-set in an weighted undirected graph

I encountered this sub-problem while working on a problem about robustness of networks against link failures. Suppose we have an undirected graph $G=(V,E)$ such that edges in $E$ have weights taking ...
5
votes
0answers
65 views

Computing a transitive completion / path existance oracle

There has been a few questions (1, 2, 3) about transitive completion here that made me think if something like this is possible: Assume we get an input directed graph $G$ and would like to answer ...
9
votes
5answers
357 views

Transitivity check vs. Transitive Closure

Is checking transitivity of a digraph not easier than (in terms of asymptotic complexity) taking the transitive closure of the digraph? Do we know any lower bound better than $\Omega(n^2)$ to ...
4
votes
0answers
105 views

Guess the bound of Lovász Path Removal Conjecture

Kawarabayashi [1] al et proved that: Theorem: There exists a function $f(k)=O(k^4)$ such that the following holds: for any two vertices $s$ and $t$ of an $f(k)$-connected graph $G$, there exists an ...
8
votes
2answers
380 views

Intuition: Odd-cycle transversal in triangle-free graphs

I conjecture that if $ G $ is a simple triangle-free graph, then there is a set of at most $ n^2/25 $ edges whose deletion destroys every odd cycle. For more information, see the 1988 paper by Erdös ...
1
vote
1answer
119 views

Figuring EasyVer problems - problems whose witness can be verified in time independent on the instance size

In a related question I've defined a class of graph problems which are verifiable using a time related only on the size of the witness: $EasyVer=\{L\subset \mathcal{G}\times \mathbb{N}| $ a witness ...
5
votes
0answers
77 views

Extending the definition of network surprise to weighted graphs

Recent research in graph clustering (also called community detection in other contexts) has shown that a definition beyond the traditional modularity (introduced by Newman, 2004) can be useful to ...
1
vote
2answers
249 views

Natural graph class with five excluded subgraphs?

I'm interested in hereditary graph classes characterized by a small number of excluded subgraphs. There are some well-known graph classes that are characterized by three or four obstructions -- ...
4
votes
2answers
98 views

Chordal graph and its clique tree

A graph $G$ is chordal if it is the intersection graph of subtrees of a tree $T$. In particular $T$ can be chosen such that each node of $T$ corresponds to a maximal clique of $G$ and the subtrees ...
4
votes
1answer
113 views

Chromatic number of planar graph with girth at least k

The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones. Girth is ...
6
votes
2answers
204 views

NPI-candidate hereditary graph property?

A graph property is called hereditary if it is closed with respect to deleting vertices. There are many interesting hereditary graph properties. Moreover, a number of nontrivial general facts are ...
1
vote
0answers
44 views

Definition of Clique vertex and separator vertex

While converting a tree decomposition of graph to Normalized tree decomposition, the definitions of clique vertex and separator vertex are used in Sequential and parallel algorithms for embedding ...