**4**

votes

**1**answer

9 views

### Analysis of the Laplacian of a random bipartite graph

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take ...

**0**

votes

**1**answer

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

**2**

votes

**0**answers

83 views

### Partitioning graph for Graph Isomorphism

Motivation: I am studying graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases required to get solution of graph isomorphism.
Construction:
$G$ is a $r$ ...

**0**

votes

**0**answers

68 views

### Graphs from which two vertices can be exchanged

A graph is vertex transitive if $x \mapsto y$ by an automorphism. Let $P$ denote the stronger property that $x \mapsto y \mapsto x$ by an automorphism.
Simple facts:
$P \rightarrow$ unimodular. ...

**0**

votes

**1**answer

88 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**0**

votes

**0**answers

42 views

### Crossing all boundaries on a map? [on hold]

In a variation on the traveling salesman problem, is there an algorithm (an approximate heuristic is fine) that finds a short, if not the shortest, path that crosses all boundaries between each pair ...

**8**

votes

**2**answers

678 views

+300

### A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...

**1**

vote

**1**answer

337 views

### Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...

**0**

votes

**0**answers

63 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...

**0**

votes

**0**answers

36 views

### Counting the k-factors of the complete graph on n vertices [on hold]

I was originally trying to solve the following problem:
10 people are in a room, and you give them a task. Their task is for each person to shake hands with exactly 3 other people in the room. How ...

**2**

votes

**2**answers

52 views

### Minimal edge color on constraints

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every even simple cycle contains an odd number ($>1$) of colors much larger than $(\log n)^\beta$ or ...

**2**

votes

**0**answers

49 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**4**

votes

**0**answers

77 views

### Does squaring a directed random graph more than double its out-degree?

As far as I know, it is an unsolved question
whether or not this is true:
If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least
double that of its ...

**1**

vote

**0**answers

218 views

### Incidence geometry and matrices

Supposing I have a $0/1$ or $\pm1$ matrix $A$ of size $m\times n$, is there a minimum $d$ (that works for every $m\times n$ $A$) such that there exists $m$ lines $r_1,\dots,r_m$, $n$ lines ...

**1**

vote

**0**answers

74 views

### Efficiently counting all paths of length n in a graph with vertex visitation contraints [closed]

I have a graph G with two classes of vertices. The first class represents no resource limitation entities and can be visited an unlimited number of times in any path traversal. The second class of ...

**0**

votes

**1**answer

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

**8**

votes

**2**answers

225 views

### Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$).
Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges
of $m$ convex sub-polygons of $P$ which ...

**2**

votes

**2**answers

127 views

### “Nice” and “nasty” partitions in graphs

Let $G=(V,E)$ be a simple, undirected graph, that is $V$ is a set and $E \subseteq [V]^2 = \{\{v,w\}: v,w \in V \land v\neq w\}$.
For $v\in V$ and $S\subseteq V$ we set $$N(v,S) = \{w\in S: \{v,w\} ...

**5**

votes

**1**answer

142 views

### Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...

**1**

vote

**0**answers

28 views

### One sided Satisfactory Partition problem

The Satisfaction Partition problem is to decide if a graph has a vertex partition (U,V) into non empty parts where each vertex has as many neighbours in its part as in the other part. This problem is ...

**1**

vote

**2**answers

107 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

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

**5**

votes

**0**answers

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

**1**

vote

**0**answers

33 views

### Weak law for component count of Erdos-Renyi random graphs

Penrose and Yukich derive a weak law for functionals of binomial point processes, which implies a law of large numbers for the component count of random geometric graphs. Do similar results exist for ...

**1**

vote

**0**answers

94 views

### From Planar Graphs To Tangent Circles

I have a conjecture:
"For each planar graph with vertices $V_1, V_2,\ldots, V_n$ there exist disjoint circles $w_1,w_2,\ldots,w_n$ in the plane, such that for every $i,j$, $w_i$ is tangent to $w_j$ ...

**6**

votes

**1**answer

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

**2**

votes

**1**answer

59 views

### Images of interval edge coloring

I found out the definition of interval edge colorings, concept put by Kamalian in various papers but could not find a graph depicting an example. Where can I find pictures of explicit examples of ...

**8**

votes

**1**answer

196 views

### Smallest strongly regular graph whose automorphism group is not vertex transitive?

I'm looking for a small strongly regular graph whose automorphism group is not vertex-transitive.
This answer to a different question shows that the Chang graphs on 28 vertices are such graphs. Is ...

**12**

votes

**1**answer

434 views

### Drawings of complete graphs with $Z(n)$ crossings

Hill conjectured that the minimum number of crossings in a drawing of the complete graph $K_n$ in the plane is exactly
$$Z(n) = \frac{1}{4} \bigg\lfloor\frac{n}{2}\bigg\rfloor ...

**12**

votes

**1**answer

148 views

### Reconstruction Conjecture: are almost all digraphs reconstructible?

The Reconstruction Conjecture for simple graphs remains unresolved. Most attempts I've seen at resolving the conjecture aim at proving it to be true (or partially true). I don't believe there is a ...

**0**

votes

**1**answer

97 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

**0**answers

109 views

### Cayley graphs with special subgraphs and some related problems

I asked some questions about finite Cayley graphs with special type of subgraphs which has been answered by Dear Prof. Godsil. It can be seen in the MO page with address:
Cayley graphs and its ...

**0**

votes

**1**answer

103 views

### Two graph structures on $\text{Hom}(G,H)$

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, ...

**1**

vote

**0**answers

55 views

### Interpreting (Fiedler) spectral bisectioning

I would appreciate help on how to interpret the results of spectral bisectioning of a graph.
Given a $G=(V,E)$ with size $N$ represented by $Q$ its Laplacian matrix where the eigenvalues are ordered ...

**0**

votes

**2**answers

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

**12**

votes

**1**answer

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

**19**

votes

**5**answers

2k views

### The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...

**5**

votes

**1**answer

81 views

### Resource Constrained Routing with Refueling

What are good algorithms (resp. models) for calculating optimal or near optimal routes while taking into account fuel consumption, options for refueling and, limited tank capacity?
Especially modeling ...

**20**

votes

**1**answer

247 views

### A small unavoidable collection of subgraphs

What is the smallest number S(k,n) of unlabeled graphs on k vertices such that every simple graph on n vertices contains at least one of these as an induced subgraph?
I'd like to avoid exhaustive ...

**4**

votes

**0**answers

45 views

### Existence of certain graph gadget related to coloring odd hole free graph

Wondering about the existence of graph gadget related to coloring
(or 3-coloring) odd hole free graphs.
Let $G$ be simple $k$-chromatic connected graph with two
vertices $u,v$.
Is it possible $G$ to ...

**1**

vote

**0**answers

138 views

### Complexity of reordering a matrix which consists independent sub matrices

Introduction:
Given a matrix A of a $k$ regular graph G. The matrix A can be divided into 4 sub matrices based on adjacency of vertex $x \in G$.
$A_x$ is the symmetric matrix of the graph $(G-x)$, ...

**3**

votes

**1**answer

156 views

### “Canonical” graph structure on $\text{Hom}(G, H)$

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq [V]^2 := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such that $\{v, ...

**8**

votes

**2**answers

343 views

### Matching number and chromatic number

If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...

**4**

votes

**0**answers

141 views

### What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...

**2**

votes

**0**answers

42 views

### Maximum cardinality general factor of a graph

Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...

**0**

votes

**0**answers

42 views

### Enumeration of simple graphs with given degree distribution/sequence [duplicate]

Is there any exact formula for asymptotic/exact enumeration of simple graphs with given degree sequence? I just found some results about it, but the formula is hold on for some conditions, for example ...

**1**

vote

**0**answers

105 views

### What are constructions for induced $C_5$-free graphs?

During a recent workshop, the question came up whether there are some constructions for graphs that are induced $C_5$-free, but they contain "everything else," so we don't want to forbid $C_5$'s, ...

**13**

votes

**1**answer

877 views

### How many labelled disconnected simple graphs have n vertices and floor((n choose 2)/2) edges?

I would like to know the asymptotic number of labelled disconnected (simple) graphs with n vertices and $\lfloor \frac 12{n\choose 2}\rfloor$ edges.

**1**

vote

**0**answers

29 views

### Small degree vertices in an epsilon-tough graph

We say that a graph is t-tough if by deleting a set if vertices $S$, the resulting graph will have at most $|S|/t$ connected components. We say that a graph is minimally t-tough if the deletion of an ...

**4**

votes

**0**answers

86 views

### Prove or disprove a claim about covering a polytope by convex polytopes in a certain way

Here is the claim:
Given a polytope $K$ in a unit ball in $\mathbb{R}^d$, there exists a universal constant $C(d)>0$ depending only on $d$ and a countable collection of convex polytopes ...