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
23 views

Random Spanning Tree Edge Probability [on hold]

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees. The problem has many parts, but there are two hints to help with the more complicated problems Figure ...
0
votes
0answers
36 views

Are there any special properties of graph eigenvalues of perfect matchings?

Say if the graph is just a perfect matching of its vertices OR if it is an union of a few perfect matchings OR its an union of a few perfect matchings and a part of another? Anything if one further ...
-1
votes
0answers
55 views

What is the characterization of a graph Laplacian? [on hold]

Given a matrix, what properties must it have so that its ensured that there exists a graph whose Laplacian it would be? (...may be you can consider weighted and unweighted cases separately...) And ...
7
votes
0answers
128 views

Could there be an exact formula for the Ramsey numbers?

Let $R(k)$ denote the diagonal Ramsey number, i.e. the minimal $n$ such that every red-blue colouring of the edges of $K_n$ produces at least one monochromatic $K_k$. Is it possible that there ...
3
votes
1answer
68 views

Strongly asymmetric graphs

Asymmetric graphs are graphs that have a trivial automorphism group $\textrm{Aut}(G)$, i.e. the only graph isomorphism from $G$ to itself is the identity. Let's call a graph $G$ strongly asymmetric ...
0
votes
0answers
54 views

Number of graphs with M edges that does not contain K-clique [on hold]

If we consider the space of graphs $G(n,M)$ where $M$ denotes the number of edges. Is there any known way of calculating the number of graphs within this space that does not contain any k-cliques? Can ...
8
votes
1answer
175 views

Vertex-primitive graphs with two vertices having almost the same neighbourhood

Hypothesis: Let $\Gamma$ be a vertex-primitive graph with two vertices $u$ and $v$ such that $$|N(u) \cap N(v)|=|N(v)|-1$$ Question: Is it true that $\Gamma$ must either be a complete graph or have ...
0
votes
1answer
75 views

Finding nodes with a particular weight in a graph

Say that an edge $e$ is incident to a node $v$ if one of its two extremes is $v$. Then we can also say that $v$ is hit by $e$. We might define the notion of "weight of a node $v$" as the sum of all ...
5
votes
1answer
78 views

Isomorphic Hadwiger graphs

Let $G$ be a graph, then we define its Hadwiger graph $\textrm{Hadw}(G)$ in the following way: $V(\textrm{Hadw}(G)) = \{S\subseteq (V(G): S\neq \emptyset\textrm{ and } S \textrm{ is connected}\}$; ...
2
votes
1answer
178 views

Counting Ribbon graphs

Let $G$ be a ribbon graph (sometimes called fat graph) with $v$ vertices and $e$ edges. Furthermore each vertex is of degree $d$. Q) What is the number of $G$ with the above properties? I mean does ...
0
votes
1answer
149 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 ...
2
votes
0answers
41 views

relationship of max-sat and min-cut in theory and practice

I have been using MAX-SAT solver to obtain the exact ground state of ising spin glass model: For 1D periodic model, for systems with 50 binary variables and interaction range of 15th nearest ...
5
votes
1answer
123 views

Number of median graphs?

What is the number of $n$-vertex median graphs? These graphs generalize hypercubes and trees, and have many applications. It seems unlikely that a closed form expression is known, so I would also be ...
2
votes
3answers
537 views

Koebe–Andreev–Thurston theorem - where can I find a proof?

Koebe–Andreev–Thurston theorem (known also as the circle packing theorem) says that any planar graph can be realized by a set of (interior-) disjoint disks corresponding to vertices, such that two ...
3
votes
1answer
148 views

Determinant of the oriented adjacency matrix of a tree

Let $(V,E)$ be a finite oriented directed graph, with vertices and edges ordered, and $M$ the $|V|\times |E|$ matrix with entries $$ m_{ve} = \begin{cases} 1 &\text{if $e$ points at $v$}\\ -1 ...
1
vote
0answers
36 views

Solutions for n such that the path number to the n-th node is also n in a complete, rooted, ordered k-ary tree

The path to find the $n$-th node within a complete, rooted, ordered $k$-ary tree can be represented by a number to the base $(k+1)$ that contains no zero digits. See A245905 in OEIS as an example for ...
1
vote
1answer
64 views

Coloring algorithm maximising color difference between neighbors

Consider a graph and a set of ordered colors ${\cal C} = \{1,2,\cdots,C\}$. I want to color each node $i$ with a color $c_i\in{\cal C}$ so as to maximize the minimum color difference between two ...
-2
votes
1answer
77 views

how to reduce 3-colorable graph to this? [closed]

suppose we have a finite set X and a set S of subsets of X and we want to determine is there a subset S' of S such that all members of X belong to exactly one set in S' I think the best problem to ...
3
votes
1answer
113 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 ...
0
votes
0answers
11 views

matching Robinson-Foulds distance and way to compute RF dist in Phylip

In Comparison of Phylogenetic Trees, Robinson D.F. and Foulds L.R., didn't show how to compute the RF distance between trees, counting the different partition generated by the removing of an internal ...
0
votes
1answer
30 views

Is it known whether Minimum Cost Multicut is APX-hard?

My questions is concerned with the following problem: Given an undirected graph $G = (V, E)$ and (edge costs) $c \in \mathbb{Z}^E$, $$\min \left\{ \sum_{e \in E} c_e x_e\ \middle|\ x \in \{0,1\}^E \ ...
-2
votes
0answers
42 views

when a given graph is 3-colorable? [closed]

I want to use graph 3-colorability to prove a problem is NP-complete But I'm not sure when a given graph is 3-colorable. I think if it doesn't have any node to be connected to all 3 vertices of a ...
-4
votes
0answers
62 views

About diagonal entries of the graph Laplacian [on hold]

[..in the following you can assume its a regular graph if necessary..] Is anything special known about them? Are they characterized in any other way? Is the largest diagonal entry in any power of ...
7
votes
4answers
203 views

4-regular graph with every edge lying in a unique 4-cycle

What are all 4-regular graphs such that every edge in the graph lies in a unique-4 cycle? Among all such graphs, if we impose a further restriction that any two 4-cycles in the graph have at most one ...
0
votes
0answers
75 views

independent subset problems [on hold]

I'm interested in the following which i suspect is probably a well studied problem. Given a set $N=\{1,2,...,n\}$ and $M=\{1,2,...,m\}$ consider a map $$f:N\rightarrow 2^{M}$$ (elements of $N$ to ...
9
votes
2answers
374 views

Can a parent and child node have the same type in a well-founded digraph tree?

$\newcommand\toward{\rightharpoonup}$It would help me to understand something in a current research project if someone could provide an example of directed graph $\langle G,\toward\rangle$ with the ...
1
vote
1answer
65 views

What is “graph-directed iterated function”?

Im translating an article about Rauzy fractal and I ran into this sentence: ...
4
votes
1answer
250 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 ≥ ...
0
votes
0answers
44 views

$\Omega(G)$ is homeomorphism to $\Omega(T)$ [closed]

Is it possible that the end set of graph $G$ is homeomorphism to the set of end for every spanning tree of $G$ where $G$ has a cycle. In other hand, for given graph $G$ and spanning tree $T$ of $G$. ...
1
vote
1answer
103 views

NP hard problems on UD graphs

I'm reading up on NP hard problems in Unit Disk graphs. I'd like to point out i'm fairly new to this NP hard stuff so i'm trying to get around how to prove something is NP hard. ...
22
votes
6answers
1k views

Shortest grid-graph paths with random diagonal shortcuts

Suppose you have a network of edges connecting each integer lattice point in the 2D square grid $[0,n]^2$ to each of its (at most) four neighbors, {N,S,E,W}. Within each of the $n^2$ unit cells of ...
0
votes
1answer
30 views

Petersen 2-factor decomposition theorem for directed graphs

Petersen proved that every 2k-regular graph can be decomposed into k disjoint 2-factors. I would like to know that is it true that if G is a directed regular graph (d_out(v)=d_in(v)=k), then can G be ...
10
votes
1answer
665 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
1answer
132 views

Graph automorphism that swaps two pairs of nodes

Suppose we have two automorphisms on a graph $G$ such that each one swaps a separate pairs of vertices. Is it possible to construct (or prove the existence of) a third automorphism that swaps both ...
0
votes
1answer
54 views

Intersection graphs

Does anybody know of a paper which proves that finding the maximum independent set in geometric intersection graphs is NP hard? Even general intersection graphs?
5
votes
3answers
292 views

Visualizing a graph

I have a finite but huge metric graph with say 1000 vertices. It comes say as 10000x10000 symmetric matrix filled by $0,1,\dots$ and $\infty$; 0's on the diagonal and $\infty$ is for pairs of vertices ...
7
votes
4answers
266 views

Do there exist sparse graphs with large crossing number?

Does there exist a sequence of graphs $\{ G_n \}$ such that $G_n$ has $n$ vertices, the number of edges of $G_n$ is $O(n)$, and the crossing number of $G_n$ is $\Omega(n)$? In particular, do ...
2
votes
1answer
83 views

irregular pairs in half graphs - Szemeredi regularity

Szemeredi's regularity lemma is a well-known result about partitioning large graphs into pieces such that most pairs of pieces are "regular". The precise statement takes a bit of detail so I'll just ...
0
votes
0answers
79 views

Does the weak Hadwiger conjecture imply the Hadwiger conjecture?

For any cardinal $\kappa$, let $K_\kappa$ denote the complete graph on $\kappa$. We consider the following statements: (H) If $G$ is a graph and $\chi(G) = \kappa$ then $K_\kappa$ is a minor of $G$. ...
2
votes
1answer
210 views

Cospectrality and dimension of graphs

Firstly, I apologize if the question is long. I appreciate any helpful answers and ideas. In the following all graphs are simple and connected. Let $G$ be graph with vertex set ...
12
votes
0answers
163 views

Coloring the edges of a torus graph

Question:Consider the $2k \times 2k$ grid graph on a torus. Is it true that for every $2$-coloring of the edges, there is an antipodal pair of vertices connected by a path that changes colors at most ...
9
votes
1answer
298 views

Shortest Paths in the “Cantor Graph”

First, let me explain, what I understand by a "Cantor Graph": it is an infinite, directed graph with self loops and countably many vertices labelled with the natural numbers; every ordered pair of ...
9
votes
3answers
2k views

Lagrange four-squares theorem: efficient algorithm with units modulo a prime?

I'm looking at algorithms to construct short paths in a particular Cayley graph defined in terms of quadratic residues. This has led me to consider a variant on Lagrange's four-squares theorem. The ...
0
votes
0answers
48 views

Expected number of distinct nodes visited in a directed bipartite graph [migrated]

Let $G = (V,E)$ be a directed bipartite graph with $V = \{I \cup O\}$ where $\left\vert{I}\right\vert = n$ and $\left\vert{O}\right\vert = m$. All the edges start from a vertex in $I$ and end on a ...
7
votes
3answers
343 views

Is there a continuous analogue of Ramanujan graphs?

I think it might help to think of the following definition of a Ramanujan graph - a graph whose non-trivial eigenvalues are such that their magnitude is bounded above by the spectral radius of its ...
6
votes
2answers
224 views

Counting valid coordinates

We are given a matrix $D = (d(i,j))_{1 \leq i,j \leq n}$ such that $d(x,z) \leq d(x,y) + d(y,z)$ for each $1 \leq x,y,z \leq n$. It is also known that $d(x,y) \in \mathbb{N}$ (In this question $0 \in ...
1
vote
1answer
136 views

Probability of each edge in K-clique [closed]

For $c \in R$ and $k \in N$, $k \geq 3$ let $p_{k,c} := n^{\frac{−2}{k+1}}log^c(n)$. I would like to prove that exists $c\in R$ such that every edge in the random graph $G(n,p_{k,c})$ lies in a copy ...
4
votes
0answers
106 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' ...
0
votes
1answer
87 views

How to solve the opposite of max flow problem? [closed]

Each edge in graph has a minimum bound instead of a maximum capacity. The goal is to find the minimum flow such that every edge in graph has flow larger than it's lower bound. I tried to use Ford ...
0
votes
1answer
69 views

Using upper bound information in graph search

I am using A* (A-Star) to search a graph. A* algorithm takes advantage of the information $h(x)$, which is a lower bound of the distance between a vertex $x$ and the destination vertex. In other ...