**-6**

votes

**1**answer

92 views

### Do degrees determine the chromatic number?

Suppose $G, H$ are finite, simple, undirected graphs and there is a bijection between the vertex sets $\varphi:V(G) \to V(H)$ such that for all $v\in V$ we have $$\text{deg}_G(v) = ...

**5**

votes

**0**answers

111 views

### Complexity of graph isomorphism

Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time:
$$ \exp(O(\log^c n)) $$
where $n$ is the number of vertices.
What is the best bound we have for $c$? (The ...

**4**

votes

**2**answers

194 views

### Algorithms for finding graph isomorphisms

I was wondering if anybody knows where I can find some information about the current (practical) algorithms for finding graph isomorphisms. I've joined the bandwagon and wrote my own which I would ...

**3**

votes

**1**answer

74 views

### Let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph?

As the title says, let $S$ be the nonempty set of strongly regular graphs with given parameters. Must $S$ contain vertex transitive graph?
I suspect the most likely counterexample would be $|S|=1$.

**5**

votes

**2**answers

122 views

### “Common-neighbor-regular” graphs

Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{w\in V:\{v,w\}\in E\}$.
We say that $G$ is $k$-common-neighbor-regular if for all $v\neq w\in V$ we have $|N(v)\cap ...

**3**

votes

**1**answer

83 views

### Tournament whose large subtournaments contain no automorphism

For sufficiently large $n$, it is known that most tournaments of size $n$ contains no nontrivial automorphism, though I forgot the reference.
For sufficiently large $n$, does there always exist a ...

**4**

votes

**1**answer

120 views

### Representing a graph's vertices as linear combinations of paths

I have a (directed graded) graph $G=(V,E)$ with two distinguished subsets of $V$: sources and destinations. I am to show that the set of indicator functions of paths starting in a source and ending in ...

**5**

votes

**1**answer

191 views

### Construction of a graph

To construct a specific kind of undirected graph $G=(V,E)$, which $|V|=n>2$. For convenience, label the vertices with $v_1,v_2,\dots ,v_n\in V$, and $(v_i,v_j)\in E$ means there is a edge between ...

**0**

votes

**0**answers

54 views

### Tight bound of Turan number for K_{1,t,t}?

I'm looking for a tight bound for Turan number $ex_2(n,K_{1,t,t})$, where $K_{1,t,t}$ is the complete 3-partite graph with parts of size 1, t, and t.
The motivation is that we now ...

**0**

votes

**0**answers

73 views

### Perfect matchings that never combine to form cycle union cover

Can there be exponential number (in terms of vertices) of perfect matchings on a bipartite graph so that no combination of them yields a union of cycles that cover all vertices?
Is there a way to ...

**0**

votes

**0**answers

60 views

### A representation problem on graphs

Given adjacency matrix $A\in\{0,1\}^{n\times n}$ of a graph denote $A(y,z)$ to be matrix where $0$ is replaced by $z$ and $1$ by $1-z$ on the non-diagonals (replace diagonals by $y$). Denote the ...

**0**

votes

**0**answers

33 views

### Question about number of faces for regular graphs

I came upon the following problem. Consider a regular 3-graph with faces of degree $2, 3, 4, 5$, 4-graph and faces of degree $2, 3$ and 5-graph with faces of degree $2, 3$. Are there any such graphs ...

**3**

votes

**1**answer

94 views

### Menger's Theorem for planar triangulations

I was reading the paper "Planar separators" by Alon, Seymour and Thomas (available on the first author's webpage). They consider a planar triangulation, that is, a maximally planar graph $G$ drawn in ...

**4**

votes

**1**answer

79 views

### The minimum number of Hamiltonian paths in a strongly connected tournament of order $n$

For $n\ge3$ let $a(n)$ be the minimum number of Hamiltonian paths in a strong (i.e., strongly connected) tournament of order $n.$
Where is $a(n)$ discussed in the literature? Is the exact value ...

**2**

votes

**1**answer

86 views

### Removing cycles in a directed graph by swapping edges orientation

I have the following problem: let $G$ be a finite directed graph with $V$ vertices $v_i$ and $E$ (directed) edges $e_j$. I know that if an edge $e_k = (v_i, v_j)$ is in the graph, then the opposite ...

**0**

votes

**0**answers

25 views

### A measurement for vertex- and edge failure sensitivity

I want to have a metric that helps me judge how independent different paths in one graph are.
So here are my assumptions:
A graph consists of a set of vertices ($V$) and edges ($E$).
A path ...

**1**

vote

**0**answers

97 views

### Extending continuous functions from $\partial X$ to $X\cup \partial X$

Consider a proper geodesic hyperbolic space $X$ (in the sense of Gromov). Let $\partial X$ be its Gromov boundary. Consider a complex-valued continuous function on the boundary $f\colon\partial ...

**0**

votes

**1**answer

88 views

### Topology on $\omega\times\omega$ such that topologically connected equals graph-connected

For any set $X$ we define $[X]^2 =\big\{\{a,b\}: a, b \in X\text{ and }a\neq b\big\}$.
Let $$E = \big\{\{(a_1, a_2), (b_1, b_2)\}\in[\omega\times\omega]^2: |a_i-b_i| = 1\text{ for some } ...

**0**

votes

**0**answers

30 views

### For which matrices deciding permutation similarity is polynomial?

Q1 For which matrices deciding permutation similarity is polynomial?
It is not easier than graph isomorphism (and very likely is equivalent to it).
If necessary, assume the entries are ...

**0**

votes

**0**answers

39 views

### Is the Hadwiger number reconstructible?

Let $G, H$ be two finite, simple, undirected graphs. We call them "reduce-by-1"-isomorphic, or $r_1$-isomorphic for short, if there is a bijection $\psi: V(G) \to V(H)$ such that for all $v \in V(G)$ ...

**0**

votes

**1**answer

107 views

### “Reduce-by-1”-isomorphic graphs

Let $G, H$ be two finite, simple, undirected graphs. We call them "reduce-by-1"-isomorphic, or $r_1$-isomorphic for short, if there is a bijection $\psi: V(G) \to V(H)$ such that for all $v \in V(G)$ ...

**0**

votes

**0**answers

45 views

### Approximation to colouring for bounded degree graphs

I have already asked one question on colouring, this question is more specific.
Given a bounded degree graph $G$ with $\Delta(G)=2d$, is there a well know algorithm to achieve an approximation ratio ...

**3**

votes

**0**answers

72 views

### What is the complexity of finding a third Hamilton Cycle in cubic graph?

According to Smith Theorem: if a cubic graph has a hamilton circuit then it must have a second one. SMITH : Given a Hamilton circuit in a 3-regular graph, find a second Hamilton circuit. It is known ...

**2**

votes

**0**answers

132 views

### Is the class of Heyting algebras originating from directed graphs a variety?

The category RefGph of reflexive directed graphs
is the functor category $\hat{∆}_1=\mbox{Fun}(∆^◦_1,$Set), where $∆_1$ is
the simplex category truncated at level 1.
Hence the poset Sub(X) of ...

**1**

vote

**1**answer

74 views

### Graph colouring for bounded degree graphs

I'm fairly new to colourings on bounded degree graphs i'm interested in the following questions,
For planar graphs with bounded degree $4$ is finding the colouring number $NP$-hard? So is ...

**1**

vote

**1**answer

68 views

### Intersection number of categorical product of graphs

Let $G, H$ be finite, simple, undirected graphs. Suppose $i(G), i(H)$ are their respective intersection numbers.
If $G\times H$ denotes the categorical product of graphs, what is $i(G\times H)$ in ...

**2**

votes

**1**answer

38 views

### Generalizing series-parallel digraphs with feedback

There are common definitions of series-parallel (SP) graphs and digraphs: the basic idea is as follows. A SP graph (or digraph) has two distinguished vertices $s$ ("source") and $t$ ("target"). The ...

**2**

votes

**1**answer

125 views

### Product and coproduct for bipartite graphs

Consider the category $BiGraph$ of bipartite graphs (vertices are named "places" and "transitions" like in Petri nets) and continous maps. A subgraph is named open iff it is place-bordered, and a map ...

**8**

votes

**1**answer

135 views

### Non-isomorphic graphs with isomorphic edge vectors

Let $G$ and $H$ be graphs on the vertex set $\{1, \ldots, n\}$ and let $(e_i)$ be the standard basis of $\mathbb{R}^n$. For each edge $\{i,j\}$ define edge vectors $e_i - e_j$ and $e_j - e_i$ in ...

**5**

votes

**1**answer

71 views

### Majority coloring for directed graphs

I came up with the following coloring concept when studying neural networks (which are often modelled using directed graphs). No idea whether there is already an established name for it.
If $X$ is a ...

**3**

votes

**0**answers

46 views

### Number of Hamiltonian paths in the Hoffman-Singleton graph/Moore graphs?

Does anyone happen to know how many Hamiltonian paths are in the Hoffman-Singleton graph, or have any idea on how I could count such paths?

**0**

votes

**1**answer

76 views

### Majority colorings

If $X$ is a non-empty set, we say that $M\subseteq X$ is a majority if $|M| > |X\setminus M|$.
Let $G=(V,E)$ be a finite, simple, undirected graph. For $v\in V$ we set $N(v)=\{x\in V: \{x,v\} \in ...

**4**

votes

**3**answers

73 views

### Name for directed graphs with “balanced cycles”

Does the following class of graphs have a name?
I'm interested in directed graphs with the following property: for every cycle (of the underlying undirected graph) half of the edges go in one ...

**0**

votes

**0**answers

21 views

### When are the cardinalities of 2-factors in a graph equal?

Given a graph $G$, if we can partition the edges into pairwise disjoint subsets of $G$, such that the union of all the subsets is equal to the edgeset of G, then this is a decomposition. If such a ...

**6**

votes

**1**answer

100 views

### The number of Hamiltonian paths in a tournament

If $h(T)$ denotes the number of (directed) Hamiltonian paths in the tournament $T,$ what is the range of $h(T)$ as $T$ ranges over all (finite) tournaments $T$?
By a classical theorem of Rédei ...

**2**

votes

**2**answers

172 views

### Decomposing a graph into n-cycles [closed]

Suppose I have a strongly $k-regular$ graph $G$, of size $v$, where every vertex is $N>0$ $n-cycles$, for $at least$ one value of $n$ that divides $v$. Can we cut edges from $G$ in such a way ...

**1**

vote

**1**answer

80 views

### A possible GI isomorphic problem

Here I try to seek if restricting the structure of permutations would still keep GI property.
Given a $2n$ vertex undirected graph whose vertices are partitioned arbitrarily in pairs to say WLOG ...

**2**

votes

**1**answer

69 views

### Directed edge-colouring

I'm interested to know whether the following problem is NP-complete or if there is an algorithm to solve it.
Suppose we are given a directed graph $G=(V,E^{\rightarrow})$ and we want to colour the ...

**1**

vote

**0**answers

52 views

### Harborth conjecture and polyhedra

Harborth conjecture state that every planar graph can be drawn on a plane only using staight line segments of rational or integral edge length.
( There is a good mathoverflow page for this conjecture, ...

**0**

votes

**2**answers

352 views

### Graphs determined by sets of consecutive integers

Given a set of positive integers, its P-graph is the graph whose vertex set consists of those integers, two of which are joined by an edge if they have a common divisor greater than 1, that is, they ...

**0**

votes

**1**answer

128 views

### Infinite graph with degrees given

Let $\kappa$ be an infinite cardinal and suppose $$n, d: \kappa \to \big((\kappa+1)\setminus \{0\}\big) = \{1, \ldots, \kappa\}$$ are arbitrary functions.
Is there $E \subseteq \big\{\{x,y\}: x\neq y ...

**0**

votes

**0**answers

57 views

### On symmetric difference of $k$-partite perfect matchings

Suppose we have a bipartite graph we know that symmetric difference of any two perfect matchings is union of even cycles.
Conversely when is it true that every union of even cycles comes from ...

**0**

votes

**0**answers

24 views

### Tree decompositions in linear hypergraphs

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a finite 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$ ...

**1**

vote

**0**answers

49 views

### Tree-chromatic number and Hadwiger number

Let $G=(V,E)$ be a finite, simple, undirected graph. For any set $X$ we set $[X]^2 := \big\{\{x,y\}: x\neq y \in X\big\}$. If $T$ is a tree, then a map $W: V(T)\to {\cal P}(V(G))$ is called a ...

**4**

votes

**2**answers

142 views

### All pairs shortest path with maximum distance

I didn't succeed to find an algorithm that finds the shortest path in a weighted non directed graph between all pairs of nodes whose shortest path distance are inferior to a specific number. I think ...

**1**

vote

**1**answer

223 views

### Good graph theory and combinatorics book

I am looking for a book about graph theory and combinatorics. I am studying the routing problem in communication networks, therefore my interest is on a book with a wide set of problems and examples.
...

**4**

votes

**1**answer

145 views

### Convex polyhedra, combinatorial types and Symmetry

Steinitz theorem says that combinatorial types of convex polyhedra is identified with 3-connected planar graph, called by a polyhedral graph.
A symmetry of polyhedral graph means that a vertex ...

**1**

vote

**2**answers

82 views

### Is this special line graph of a graph a known concept?

Let $G=(V,E)$ be an undirected graph. We form a graph $H=(V',E')$ from $G$ such that
$V' = V \cup \{ w_e \mid e \in E \}$, and
$E' = \{ aw_e, bw_e \mid ab = e \in E \} \cup \{ w_e w_f \mid e,f ...

**0**

votes

**1**answer

66 views

### Vertex cover of regular graph

(1.) How small can set $S$ of vertices in any regular undirected graph $G$ on $n$ vertices with degree $\Omega(n^\alpha)$ where $\alpha\in(0,1)$ can be such that every edge in the graph is incident on ...

**2**

votes

**0**answers

79 views

### Dicks–Dunwoody almost stability theorem

In the book 'Groups acting on graphs' (1989), Dicks and Dunwoody prove the following theorem (paraphrased):
Let $G$ be a group acting on a set $E$, let $E'$ be a subset of $E$ and let $V$ be the set ...