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

**2**

votes

**0**answers

80 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

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

**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

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

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

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

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

**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\} ...

**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

**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

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

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

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

**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$ ...

**8**

votes

**2**answers

677 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$ ...

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

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

**1**

vote

**0**answers

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

**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

**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, ...

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

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

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

**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, ...

**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)$, ...

**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, ...

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

**3**

votes

**1**answer

85 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, ...

**0**

votes

**0**answers

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

**-1**

votes

**1**answer

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

**5**

votes

**2**answers

238 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

**0**answers

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

**2**

votes

**0**answers

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

**11**

votes

**1**answer

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

**6**

votes

**1**answer

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

**0**

votes

**0**answers

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

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

**5**

votes

**1**answer

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

**4**

votes

**0**answers

37 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

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

**1**

vote

**1**answer

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

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

**6**

votes

**2**answers

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