**5**

votes

**2**answers

201 views

### Four Dimensional Rook Domination

Let $\gamma(G)$ denote the domination number of a graph, and $G\,\square\,H$ denote the cartesian product of two graphs. Then $K_8\,\square\, K_8$ is the rook graph, whose vertices are the squares of ...

**3**

votes

**1**answer

54 views

### $P_3$-factors for 3-regular, 3-connected cubic graphs

Suppose that $G=(V,E)$ is a simple graph.
We know if $G$ is 3-regular, 3-connected and $|V|=4k$ for some $k\in \mathbb{N}$, then $G$ has a $P_4$-factor.
Question. Let $G=(V,E)$ be 3-regular, ...

**-2**

votes

**0**answers

22 views

### Determining the inside and outside of planar graphs by means of ray shooting [on hold]

Consider an embedding of a circle in the plane $\mathbb{R}^2$ splitting the plane into an outside and inside region (Jordan-Brouwer). Consider next a point $p$ in the plane.
A standard procedure for ...

**5**

votes

**1**answer

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

**0**

votes

**0**answers

11 views

### Complexity of edge coloring graphs of sufficiently large maximum degree

I am interested in the complexity of edge coloring
graphs with $\Delta(G) > |V(G)|/3$.
This is closely related to the Overfull conjecture (OC).
Conjecture/Question: If a simple graph G with n ...

**0**

votes

**1**answer

37 views

### How to generate computational data in graph theory?

For a given number of nodes how many non-isomorphic graphs are available? Might be this is an open problem. For less number of vertices some computational statistics available.
I want to get all ...

**0**

votes

**1**answer

197 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

**0**answers

50 views

### Cayley graph of dihedral group is isomorphic to which kind of graphs? [on hold]

Let D_{2n}= be dihedral group of order 2n. Also let D_{2n}= in which 1\ notin S=S^{-1}.
In this case Cay(D_{2n}, S) is isomorphic to which kind of graphs? This is my conjecture that this graph is ...

**8**

votes

**3**answers

378 views

### Disjoint Maximum Independent Sets in $alpha$-critical graphs

Let $G$ be an undirected, simple graph, and let $\alpha(G)$ denote the independence number of $G$, i.e., the size of a maximum independent set (stable set) in $G$. A graph is $\alpha$-critical if for ...

**-6**

votes

**0**answers

26 views

### Identify a curve from bunch of numerical data [on hold]

I am trying to identify/compare a similar curve with the data I have.
Data format:
X, Y:
(1, 0.01),
(2, 0.02),
(3, 0.03),
(2, 0.04),
(n, k),
Lets say I have a plot or values which will generate a ...

**3**

votes

**0**answers

75 views

### Application of finding shortest paths on Cayley graphs

For a fixed integer number $m$, Consider Cayley graph defined by all m-cycles in Symmetric group $Sym(n)$.
I know that for $m=2$,
there are some applications of finding shortest paths (or distance ...

**11**

votes

**1**answer

205 views

### Travelling Salesman Problem: Can the nearest neighbor algorithm be $n$ times longer than the optimal solution?

This is inspired by a recent question.
Given a positive integer $n\in\mathbb{N}$, is there a setting of finitely many points and a designated "starting point" $s$ in $\mathbb{R}^2$ such that the ...

**-1**

votes

**0**answers

85 views

### Graph Theory text for a social scientist [on hold]

I am a graduate student in Economics. I have a decent grounding in maths, but I've never studied graph theory or combinatorics. I need to study graph theory in order to analyse production networks. ...

**6**

votes

**1**answer

163 views

### Length of nearest neighbor path in travel salesman problem

Given $n$ nodes uniformly distributed in $[0,1]^2$, consider the nearest neighbor algorithm to solve traveling salesman problem, i.e., each time I select the nearest neighbor not visited so far as the ...

**21**

votes

**1**answer

1k views

### Red-blue alternating paths

Suppose we have two simple graphs on the same vertex set. We will call one of them red, the other blue. Suppose that for $i=1,..,k$ we have $deg (v_i)\ge i$ in both graphs, where ...

**1**

vote

**1**answer

109 views

### How many triangles can a connected graph with $n$ vertices and $m$ edges have?

I am very interested in the maximum number of triangles could a connected graph with $n$ vertices and $m$ edges have. For example, if $m\leq n−1$, this number is $0$, if $m=n$, this number is $1$, if ...

**2**

votes

**0**answers

33 views

### Is this infinite family of non-trivial snarks resulting from the first Celmins-Swart?

Non-trivial snark is cubic graph with chromatic index $4$, girth
at least $5$ and doesn't to contain three edges whose deletion results in a disconnected graph, each of whose components is nontrivial.
...

**0**

votes

**0**answers

12 views

### heavy subgraph searching result in pseudopatterns in tensor [closed]

I encounter problem while trying to find heavy subgraph in tensor.
I'm trying to maximize H(x,y)=1/2 summation a(ijk)x(i)x(j)y(k)
Why do I only find pseudopatterns in heavy subgraph searching in ...

**4**

votes

**0**answers

113 views

### Unique Nash equilibrium games

Multicast network design game is a special case of a general network design game (http://www.cs.cornell.edu/home/kleinber/focs04-game.pdf) in which there is a target vertex $t$ and $n$ rational ...

**0**

votes

**0**answers

71 views

### What is the diameter of the Cayley graph of $S_n$ w.r.t the generator $\{(12),(23), . . . ,(n − 1 n) \}$? [duplicate]

Given a symmetric group $S_n $ and the generator set : $S = \{(12),(23), . . . ,(n − 1 n) \}$ is there any closed form expression for the diameter of the Cayley graph generated by this set of ...

**4**

votes

**1**answer

181 views

### Large bicliques in r-partite graphs containing no independent sets having one vertex from each class

Let $G$ be a multipartite graph on $r$ classes, each containing $k$ vertices, such that there is no independent set which contains at least one vertex from each class. I believe such graphs contain a ...

**5**

votes

**1**answer

129 views

### partition of a convex set into squares

Let $P$ denote the perimeter function. It's not hard to prove that for any rectangle $R$ in $\mathbb{R}^2$, $R$ can be partitioned into a countable collection of squares $\{Q_k\}_{k=1}^{\infty}$ such ...

**0**

votes

**2**answers

93 views

### Generate all non-isomorphic partitions $\pi = \{ \{1, …, n-1\}, \{n\} \}$ for all graphs of order $n$

Let $G$ be any connected, undirected, and unweighted graph of order $n$.
Let $\pi = \{ \{ 1, ..., n-1 \}, \{ n \} \}$ be partitioning of $G$ such that always $n-1$ vertices are in the first cluster ...

**3**

votes

**1**answer

103 views

### Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of:
(A) a random graph (e.g., Erdos-Renyi graph),
(B) a small-world graph ...

**1**

vote

**5**answers

3k views

### Graduate Schools for Graph Theory [closed]

I am a rising senior in a small liberal arts college, and I was wondering if anyone could suggest me good graduate schools for graph theory. My only exposure to graph theory has been the intro graph ...

**4**

votes

**0**answers

30 views

### Digraph weak connectivity in $O(V)$ space and $O(V+E)$ time

A digraph is called weakly connected if its underlying undirected graph is connected.
You are given a digraph $G$ with $V$ vertices and $E$ edges as a read-only data structure consisting of lists of ...

**1**

vote

**1**answer

46 views

### Sizes of maximum matchings in a finite, simple, undirected graph

Let $G=(V,E)$ be a finite, simple, undirected graph. We say that a matching $M\subseteq E$ is a maximum matching if for all $e\in (E\setminus M)$ the set $M\cup\{e\}$ is not a matching any more.
...

**6**

votes

**2**answers

367 views

### Embedding of planar graphs

I've recently come across the following lemma.
Lemma (Valiant): A planar graph $G$ with maximum degree $4$ can be embedded in the plane using $O(|V|)$ area in such a way that its vertices are at ...

**0**

votes

**1**answer

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

**1**

vote

**1**answer

3k views

### efficient way to count hamiltonian paths in a grid graph for a given pair of vertices

1/ What algorithm would you use to count all the hamiltionian paths in a n x m grid graph (n and m <10) from a given starting vertice to an ending one
2/ if this grid graph have holes?
Thanks ...

**1**

vote

**2**answers

95 views

### Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...

**3**

votes

**1**answer

141 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

**4**answers

840 views

### On the spectrum of random regular graph

For a random $d$-regular graph, where $d$ can be fixed or can grow slowly with the size of the graph $n$, what can we say about its spectrum - Do you believe it has simple spectrum?
Thank you,

**20**

votes

**18**answers

27k views

### Good programs for drawing graphs ( directed weighted graphs )

Does anyone know of a good program for drawing directed weighted graphs?

**2**

votes

**0**answers

52 views

### Linear intersection number of a product of graphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties:
for $e\in L$ we have $|e|\geq 2$;
if $e_1\neq e_2 \in L$ then ...

**8**

votes

**1**answer

185 views

### Cheeger Numbers for 3-regular Graphs

A student wanted a challenging Graph Theory programming project and I had
him try to determine the maximum value of the Cheeger number (isoperimetric number) among all 3-regular graphs of order $n$, ...

**0**

votes

**1**answer

43 views

### Extracting path information for a directed acyclic graph

For a research problem I am tackling, I have a directed acyclic graph $G(V,E)$. With every node in $V$, I have a variable $y$ associated. Now, given two nodes $i$ and $j$, I would like to have the sum ...

**3**

votes

**2**answers

290 views

### Geometry, Number Theory and Graph Theory of n-gon, permutation and graph labeling?

Given $n$ and $t$ lengths $ l_i, 1\leq l_1<l_2<\cdots<l_t\leq n-1$, of directed diagonals within an $n$-gon such that $l_1+\cdots+l_t\neq 0 \pmod n)$. Does it exist a directed path within ...

**6**

votes

**1**answer

331 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 ≥ ...

**4**

votes

**0**answers

92 views

### Counting vertex-permutations of a finite tree which rip all edges

Given a finite tree $T$ with $n$ vertices labelled $1,\dots,n$, we say that a permutation $\sigma$ of $1,\dots,n$ rips all edges if $\{\sigma(i),\sigma(j)\}$
is never an edge for every edge $\{i,j\}$ ...

**1**

vote

**0**answers

35 views

### Is there a polynomial time algorithm for Poly-trees (Oriented trees) isomorphism?

In terms of graph isomorphism complexity classes Trees have a polynomial time algorithm and Directed Acyclic Graphs (DAG's) do not (so far).
What about Poly-trees (oriented trees)? These are DAG's ...

**5**

votes

**0**answers

73 views

### Graphs with no homomorphism and no minor relation

What is an example of two simple, undirected graphs $G,H$ such that
there are no graph homomorphisms between $G, H$, and
$H$ is not a minor of $G$, and $G$ is not a minor of $H$
?
Definition of ...

**4**

votes

**3**answers

172 views

### How networks with high largest eigenvalues are more robust?

In the literature, it is sometimes indicated that network with high value of largest eigenvalue (either adjacency matrix or its Laplacian counterpart) are more robust against link/node removals. ...

**2**

votes

**0**answers

51 views

### Strongly minimal covering subsets of $\text{Ind}(G)$

Let $G=(V,E)$ be any undirected, simple graph. Let $\text{Ind}(G)$ be the set of independent subsets of $V(G)$. We say that $K\subseteq \text{Ind}(G)$ is a cover (by independent subsets) if $\bigcup K ...

**0**

votes

**0**answers

42 views

### Expected length of minimum spanning trees

For a simple, finite, connected and complete graph $K_n = (V(K_n), E(K_n))$ with vertex set $V(K_n)$ and edge set $E(K_n)$, we assign a non-negative independent and identical distributed random weight ...

**0**

votes

**1**answer

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

**0**

votes

**0**answers

63 views

### Probabilities in a directed graph

Given a directed graph of "n" vertices, having on average "m" out-edges each, what is the probability that an arbitrarily chosen vertex will belong to a unique circuit?
Also, how does that ...

**12**

votes

**1**answer

834 views

### A generalization of the triangle counting problem for simple weighted graphs

One nice identity is that $$\operatorname{tr}(A^3)/6$$ counts the number of triangles of a graph with adjacency matrix $A$. It also implies that triangle counting in a graph can be performed in ...

**8**

votes

**4**answers

252 views

### Diameter of random segment intersection graph?

I have an even number of points $n$ randomly distributed (uniformly) in a disk.
Then the points are randomly connected to form $n/2$ segments, a perfect
matching.
Finally, I form the intersection ...

**0**

votes

**0**answers

65 views

### Gromov-Hausdorff distance measure between minimum spanning trees

I am trying to compare minimum spanning trees through time. I have two questions:
1-Is it possible to measure the similarity between two minimum spanning trees with Gromov-Hausdorff distance measure ...