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

2
votes
0answers
67 views

Can this graph polynomial be efficiently computed?

I am a physicist, so apologies in advance for any confusing notation or terminology; I'll happily clarify. To provide a minimal amount of context, the following graph polynomial came up in my research ...
0
votes
0answers
60 views

edge graph reconstruction conjecture : set vs multi set

Why is the edge reconstruction conjecture stated with the deck defined as the multi set of graphs formed by deleting one edge? Can someone give an example of two graphs such that the edge deleted ...
4
votes
2answers
131 views

What is the number of noncrossing acyclic digraphs?

A noncrossing graph on $n$ vertices is a graph drawn on $n$ points numbered from $1$ to $n$ in counter-clockwise order on a circle such that the edges lie entirely within the circle and do not cross ...
5
votes
0answers
46 views

Set system with prescribed intersection sizes

Questions: What is the asymptotic maximal size of a $4$-uniform (every set has 4 elements) set system $\mathcal{A}$ of subsets of $[n]$ such that, no two sets have size of their intersection $2$? In ...
4
votes
1answer
106 views

Graphs where each edge belongs to the same number of 1-factors

Let $G$ be a simple connected graph that has at least one 1-factor. We'll define: $G$ has property A iff it is edge-transitive. $G$ has property B iff each edge belongs to the same number of ...
12
votes
13answers
17k views

Good programs for drawing graphs ( directed weighted graphs )

Hi, does anyone know of a good program for drawing directed weighted graphs? Thanks
1
vote
0answers
104 views
+50

Computing the chromatic polynomial of graph modulo $x-3$

The chromatic polynomial of graph $P(G,x)$ is univariate polynomial which counts the number of colorings of $G$ with $x$ colors for natural $x$. Graph is not $k$ colorable iff $P(G,k)=0$. The ...
2
votes
0answers
91 views

special 1-factorization of regular bipartite graphs

Let $n= 2k+1, |X|=|Y|= n$ and $G= (X, Y, E)$ be a $(k+1)$-regular bipartite graph. Let $M$ be a perfect matching of $G$ having the property that every cycle of size 4 $C_4$ intersects $M$ in at most ...
27
votes
3answers
2k views

Can assignment solve stable marriage?

This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy. Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...
4
votes
1answer
207 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 ≥ ...
1
vote
1answer
159 views

3-complexes not embeddable in 3-space

My question is about embeddability of 3-dimensional complexes in R^3. Do we have something like Kuratowski's theorem for complexes in 3-space which specifies a set of minors for non-embeddability?
1
vote
1answer
97 views

Vertex transitive and edge transitive and line graph

How can we find the proof of the following statement: An undirected graph is edge transitive if and only if its line graph is vertex transitive.
22
votes
2answers
463 views

Removal of non-isomorphic edges results in the same graph

There exists a (simple unlabeled) graph on 6 nodes with a pair of non-isomorphic edges (i.e., there is no graph automorphism that sends one edge into the other) such that removal of either of them ...
12
votes
2answers
1k views

Determinants in Graph Theory

In graph theory, we work with adjacency matrices which define the connections between the vertices. These matrices have various properties in themselves. For example, their trace can be calculated (it ...
10
votes
1answer
569 views

A generalization of the triangle counting problem for simple weighted graphs

One nice identity is $$tr(A^3)/6$$ which counts the number of triangles of a graph represented with adjacency matrix $A.$ It also implies that triangle counting can be performed in subcubic time. ...
2
votes
0answers
144 views

How hard is a variant of graph automorphism problem?

I'm interested in a variant of graph automorphism problem (which is prime candidate for $NP$-Intermediate problem). Restricted GA Input: Given an undirected graph $G(E, V)$, and $\epsilon |V|/2$ ...
10
votes
2answers
458 views

Is every knot unavoidable in the embeddings of some graph?

Is it the case that, for any given knot $K$, there exists some graph $G$ whose every embedding into $\mathbb{R}^3$ (or into $\mathbb{S}^3$) contains a cycle that realizes $K$? I know the ...
3
votes
2answers
161 views

Distance between two networks

Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ...
0
votes
0answers
36 views

Complexity of graph isomorphism in $(P_4 \cup K_1,\overline{3K_2})$-free graphs

Related to this question where isomorphism preserving transformation maps triangle-free graphs to $(P_4 \cup K_1,\overline{3K_2})$-free graphs. What is the complexity of graph isomorphism in $(P_4 ...
3
votes
1answer
97 views

Graph transformation related to graph isomorphism

Basically got graph transformation related to graph isomorphism. Define $G \to G'$. $V(G')=V(G) \cup E(G)=\{v_1\ldots v_n\} \cup \{e_1\ldots e_m\}$. Call $v_i$ vertices $v'$ and $e_i$ vertices $e'$. ...
3
votes
1answer
163 views

Hamiltonian circuit

Let us consider a disk with one labelled point on the boundary and $n$ labelled points in the interior. Let T be a triangulation of the whole disk with vertices on the labelled points such that T ...
9
votes
1answer
383 views

Existence of a sink in directed graphs with a certain structure

I'm not a mathematician (I'm an economist) but I hope that this problem is sufficiently non-trivial that someone here will find it interesting. Motivation: I'm trying to model how workers decide ...
0
votes
1answer
63 views

Finding node-disjoint routes with mutually exclusive nodes in graphs

I have the following problem. I would like to know if it reduces to some standard problem in Graph theory. Particularly, I would like to know whether it is NP-hard, if yes, how to prove its ...
3
votes
3answers
292 views

Turan's theorem for connected graphs?

Using a small modification to Turáns theorem we can find the minimum amount of edges a graph $G$ on $n$ vertices must have so it does not have an independent set of size $k$. Is there a similar result ...
4
votes
1answer
449 views

Surprising connection between linear algebra and graph theory

What is the intuition for linear algebra being such an effective tool to resolve questions regarding graphs? For example, one can determine if a given graph is connected by computing its Laplacian ...
0
votes
0answers
20 views

Splitting lemma for digraph and preserving local rooted-edge connectivity?

Let $G$ be a directed graph. $\lambda(x,y,G)$ is the maximum number of edge disjoint paths from $x$ to $y$ in $G$ The local $r$-rooted connectivity of $x$ in $G$ is $\lambda(r,x,G)$. The global ...
2
votes
1answer
117 views

Minimum length path touching $n$ circles

Given $n$ non-overlapping circles of radius $1$ (i.e., the distance between the centers of any two circles is greater than $2$), how to find the minimum length path (the path can be of any form) that ...
2
votes
1answer
80 views

triangles in a graph with specified clique number

Turan's theorem tells us that if m is the number of edges in a graph with n vertices and clique number r, then 2m <= (r - 1)n^2/r. If t denotes the number of triangles, is there a similar ...
3
votes
2answers
322 views

An upper bound for number of triangles in a graph

A small inquiry about something that has been troubling me for the whole afternoon without luck: is there any known result about say simple graphs $G(V,E)$ with some property $\mathcal{P}$ such that ...
3
votes
0answers
37 views

Algorithm to construct metric space endomorphism with controlled square

Given a finite metric space $(M,d)$ with parameters $K \geq 1$ and $\epsilon > 0$, I'd like to algorithmically check for the existence of a non-identity map $\phi:M \to M$ which happens to be ...
5
votes
3answers
386 views

Relationship between triangle free graphs and their minimum degree

Let $T$ be a triangle-free graph on $n$ vertices with minimum degree $\delta$ (which can be $0$). How does one show that $n >2\delta -1$? It seems to be true for bipartite graphs, but I cannot see ...
5
votes
1answer
274 views

Bipartite Graphs arising from two k-partitions of a given Graph

Let $G$ be an $n$-chromatic connected graph. Let $(V_1, V_2, \cdots, V_n)$ and $(U_1, U_2, \cdots, U_n)$ be two partitions of $V(G)$ corresponding to proper n-colorings of $G$. Consider the bipartite ...
2
votes
1answer
82 views

About the diameter of a graph after removing orientation

This question was posted a few days ago on the Mathematics StackExchange, but so far it has not been answered. Let $G$ be a strongly connected directed graph of diameter $D$, and suppose that we ...
0
votes
1answer
46 views

N random walkers that hit node v in a graph

Consider a finite, undirected graph G, with uniform edge weights. Assume that there are n number of random walkers that will start at different nodes (lets say n=3, hence the random walkers will start ...
2
votes
1answer
148 views

Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let ...
0
votes
1answer
102 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
0answers
31 views

What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively. Evaluating it is $\#P$-complete even when restricted to ...
1
vote
2answers
165 views

Strongly connected DAG from any connected undirected graph?

I have the following question. It seems likely to be true - can anyone provide a standard reference? Given: A connected, undirected graph. Question 1: Can we assume a single direction for each edge ...
10
votes
0answers
194 views

Mixing properties of random walks on graphs [migrated]

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 ...
0
votes
4answers
108 views

about the structure of components of tensor product if more than one bipartite graph is taken

I was reading about tensor product of graphs. We know that if we take tensor product of n graphs and want this product to be a connected graph then at most one graph should be bipartite. In the book ...
7
votes
0answers
86 views

Algorithms for computing the Resilience of Graphs

The definition of resilience with a graph $G$ w.r.t to a monotone property $\mathcal{P}$ is well known. (Global resilience) Let $\mathcal{P}$ be an increasing monotone property. The global ...
32
votes
6answers
2k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
3
votes
0answers
82 views

Node covering in a random graph

Given $N$ nodes randomly placed in a $D\times D$ area, i.e., the position of each node is randomly chosen. Assume that both $N$ and $D$ are sufficiantly large. An agent can move in the area at ...
6
votes
2answers
163 views

Find multiple non-adjacent paths in a graph

Consider a non-directed graph. I want to find as many non-adjacent paths as possible from a source $s$ to a destination $t$. Two paths $P_1$ and $P_2$ are said to be non-adjacent to each other if none ...
0
votes
0answers
91 views

Reduction from permanent to $(0,1)$-permanent and implication of $P \ne NP$

Valiant shows reduction from counting the solutions of CNF formula $F$,$\#SAT(F)$ to computing permanent where $ Perm(A)= 4^{t(F)}\cdot \#SAT(F)$ for certain efficiently computable $t(F)$ and matrix ...
4
votes
2answers
218 views

Equality-preserving embeddings of finite trees

For finite trees $T_{1}$ and $T_{2}$ labelled by elements of some infinite set $S$, (we may assume that $S=\mathbb{N}$ without loss of generality), we define an equality-preserving embedding $f$ to be ...
4
votes
1answer
111 views

Product of geodesic distances

I'm working on trying to show this, but can't seem to get started. No guarantees that it is true, but other conditions on the adjacency matrix that make it true or a counter example are helpful. ...
0
votes
1answer
117 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 ...
21
votes
7answers
3k views

Spectral graph theory: Interpretability of eigenvalues and -vectors

I thought "Wow!" when I learned that the eigenvector of the adjacency matrix of a cycle graph $C_n$ corresponding to the second largest eigenvalue gives the coordinates of the vertices when equally ...
0
votes
2answers
75 views

different way of selecting a random graph

Consider having a 'base' graph $G=(V,E)$ and selecting each vertex with independent probability $p$ and having the induced subgraph of $G$ with all 'selected' points as your random graph. Has this ...