**0**

votes

**0**answers

59 views

### Computation on Random Bipartite graphs

I'm looking at a random bipartite graph $K_{\omega(n)}*K_{\omega(n)}$ where $\mathrm{log}(n)\leq \omega(n) \leq n^{1/2}$, in which each of the $\omega(n)^{2}$ edges is placed randomly with probability ...

**3**

votes

**1**answer

59 views

### Minor ordering for finite graphs

Let $\mathcal{G}_{<\omega}$ be the set of graphs $G = (V,E)$ such that $V = \{0,\ldots,n\}$ for some $n \geq 0$ and $E \subseteq \mathcal{P}_2(V) = \{\{a,b\} : a,b \in V \textrm{ and } a\neq b\}$. ...

**1**

vote

**0**answers

64 views

### Matchings in random bipartite graphs

I was wondering if anyone could point me in the direction of a text or paper which would help deal with the following problem
Suppose i am given a $K_{\mathrm{log}(n)} \times K_{\mathrm{log}(n)}$ ...

**4**

votes

**2**answers

141 views

### Graphs whose degree vectors coincide for all powers of their adjacency matrices

Let symmetric $A,B \in \{0, 1\}^{n \times n}$ denote the adjacency matrices of two simple graphs. Further let $\mathbf{1}$ denote the all-one-vector.
Now assume that $A^k \mathbf{1} = B^k \mathbf{1}$ ...

**0**

votes

**1**answer

76 views

### What is the standard name of an edge-graph

Given a graph $G=(E,V)$, I construct a graph $G'$ where the vertices of $G'$ are given by the edges of $G$ and say that two edges of $G$ are neighbors in $G'$ if they have a common vertex.
Is there a ...

**2**

votes

**2**answers

154 views

### “Homomorphism fingerprint” for graphs

Let $G, H$ be simple, undirected graphs without loops. We say that $G, H$ have the same homomorphism fingerprint if $|\text{Hom}(X, G)| = |\text{Hom}(X, H)|$ for all graphs $X$. (By graph ...

**3**

votes

**0**answers

100 views

### Cores of infinite graphs

Let $\kappa$ be a cardinal and let $\textrm{Grph}(\kappa)$ be the set of graphs $G = (V,E)$ such that $V \subseteq \kappa$ and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$.
We ...

**4**

votes

**1**answer

160 views

### What can be said about graphs if there are homomorphisms in both directions?

Let $G,H$ be simple undirected graphs without loops such that there are graph homomorphisms $f_1:G\to H$ and $f_2: H\to G$.
An easy argument shows that we have $\chi(G) = \chi(H)$, even for graphs ...

**1**

vote

**0**answers

104 views

### NP hard problems on geometric graphs

I have posted this question before but i don't feel i expressed my confusion clearly enough. So i would like to try and explain again. This is a proof of the minimum vertex cover for unit disk graphs ...

**2**

votes

**0**answers

66 views

### Total number of spanning trees of a set of graphs

Given an undirected graph G with $n$ nodes, we can compute its number of spanning trees in polynomial time using Kirchhoff's matrix-tree theorem. Now consider a more complicated setting, in which each ...

**9**

votes

**4**answers

316 views

### Are these three different notions of a graph Laplacian?

I seem to see three different things that are being called the Laplacian of a graph,
One is the matrix $L_1 = D - A$ where $D$ is a diagonal matrix consisting of degrees of all the vertices and $A$ ...

**1**

vote

**0**answers

63 views

### Max flow with minimal requirements algo problem

While applying the algorithm to solve the max flow of the network with minimal requirements on edges, I have encountered a problem.
The algorithm states:
For graph G
create an edge from target to ...

**1**

vote

**1**answer

92 views

### n-cube connectivity problem

Given $n\geq 2$, let us consider the n-cube $H_n=(V,E)$, i.e. vertex set $V$ is $\{0,1\}^n$.
Here, the edges of $H_n$ are directed, oriented by set inclusion, i.e., $(x,y)\in E$ iff $x\subseteq y$ and ...

**6**

votes

**2**answers

119 views

### Realizing a monoid as $\mathrm{End}(G)$ for some graph $G$

This question relates to Realizing groups as automorphism groups of graphs.
Given a monoid $M$, is there a graph $G$ such that the endomorphism monoid $\textrm{End}(G)$ is isomorphic to $M$?

**9**

votes

**1**answer

343 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 ...

**4**

votes

**1**answer

93 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 ...

**6**

votes

**1**answer

97 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

**1**answer

194 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 ...

**2**

votes

**0**answers

59 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 ...

**3**

votes

**1**answer

169 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 ...

**4**

votes

**3**answers

719 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 ...

**1**

vote

**0**answers

46 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 ...

**7**

votes

**1**answer

235 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

**1**answer

96 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 ...

**0**

votes

**0**answers

17 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 ...

**1**

vote

**1**answer

95 views

### What is “graph-directed iterated function”?

Im translating an article about Rauzy fractal and I ran into this sentence:
...

**10**

votes

**2**answers

446 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 ...

**7**

votes

**4**answers

258 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

**1**answer

64 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 ...

**1**

vote

**1**answer

138 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.
...

**2**

votes

**1**answer

144 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

**1**answer

59 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?

**6**

votes

**0**answers

136 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

**1**answer

104 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 ...

**12**

votes

**1**answer

287 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

**2**answers

235 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

**1**answer

38 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 \ ...

**0**

votes

**1**answer

109 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 ...

**7**

votes

**3**answers

397 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 ...

**4**

votes

**0**answers

120 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' ...

**6**

votes

**2**answers

234 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 ...

**2**

votes

**2**answers

55 views

### Deciding whether a given graph has an f-factor or not!

Given a graph $G$ with $n$ vertices and a function $f$ from $\{1,2,...,n\}$ to non-negative integers, Does there exist an efficient (for example polynomial time) algorithm, that decides whether $G$ ...

**1**

vote

**1**answer

152 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 ...

**0**

votes

**1**answer

83 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 ...

**2**

votes

**2**answers

119 views

### About the roots of the matching polynomial

Can someone kindly give me an expository reference on matching polynomial and its roots? (there is a proof that they are always real?)
I saw these two related discussions,
Roots of matching ...

**2**

votes

**0**answers

70 views

### Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?

Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and ...

**1**

vote

**1**answer

215 views

### Probability of connected graph on torus

Let $G = (V, E)$ be a graph on n vertices constructed in the following way:
Each vertex $v \in V$ is positioned uniform randomly in $[0, 1] × [0, 1]$.
Connect two vertices $u, v \in V$ if $d(v,u) ≤ ...

**2**

votes

**0**answers

53 views

### Fixing (non)-independency of a the subfamilies of finitely many events.

I'm would be interesting in any construction of a probability space with n events (n is given), where for every subset of these events, it is also given whether or not, the family is mutually ...

**1**

vote

**0**answers

54 views

### clustering in a graph on boolean functions

Fix some n and k. Consider the following directed graph: vertices are all functions $2^n\rightarrow 2^n$ and a vertex f has an edge to a vertex g for every h such that $f=h\circ g$ and h depends only ...

**3**

votes

**2**answers

298 views

### Find all faces in a graph from list of edges

I have the information from a undirected graph stored in a 2D array. The array stores all of the edges between nodes, e.g. graph[3] might be equal to [1,8,30] and represents the fact that node 3 ...