**0**

votes

**1**answer

89 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

35 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

110 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

74 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

133 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

76 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

39 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

133 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

143 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

**2**answers

91 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

47 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

79 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

22 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

105 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

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

**3**

votes

**1**answer

86 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

57 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

359 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

130 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

62 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

161 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

228 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

149 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

83 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

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

**5**

votes

**1**answer

168 views

### Heyting algebras originating from directed graphs

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

**0**

votes

**0**answers

25 views

### Statistics of Length Eccess in Shortest Path Calculations

I am trying to quantify the error that arises in the following problem:
let $\mathcal{T}$ be a tiling of the plane and the task is to calculate shortest paths in the network $\mathcal{N}$ of the union ...

**3**

votes

**1**answer

95 views

### Spectra of undirected $d$-regular graphs

Let $G$ be a undirected $d$-regular graph, that is, a graph whose all vertices have the same degree $d$. It is known that the eigenvalues $\sigma_i$, $i=1,\cdots,n$, of the adjacency matrix are real ...

**5**

votes

**1**answer

174 views

### Is there a polynomial-time algorithm to check if a signed graph contains an odd-K5 minor?

I suspect this exists, if anyone has a reference please that would be very helpful.
By signed graph, I mean each edge is designated either odd or even (e.g. as in Guenin's result for weakly bipartite ...

**0**

votes

**0**answers

23 views

### Grötzsch graph crossing number [duplicate]

can't find the proof that the crossing number of the Grötzsch graph is 5.

**4**

votes

**2**answers

250 views

### What is the independence number of this graph which is a generalization of a Kneser graph?

Let $\mathfrak{A}=\{1,2,\dots,8\}$ and construct a graph as follows. Let the vertices of the graph be the set of all $A=(\{a,b,c\},\{d,e\})$ where $a,b,c,d,e\in \mathfrak{A}$ are distinct. Two ...

**1**

vote

**0**answers

44 views

### An algorithm to compute the number of graphs of size n with a given graph as a minor

I'm looking for any results regarding computing the number of graphs of size $n$ which have a given graph $H$ as a minor. Are there any known algorithms which are more efficient than a brute force ...

**5**

votes

**1**answer

218 views

### Graph spectra and topology

This is a somewhat vague question, but I'm wondering if there has been any research into connections between the spectrum of a graph and some notion of the "topology" of that graph.
To give an ...

**1**

vote

**0**answers

61 views

### Difference in the Four Color Theorem [closed]

How is proving that any planar graph with maximum degree of four has a four coloring, different from proving the four color theorem? If they are different, then how would one prove it?

**2**

votes

**1**answer

139 views

### Counting growing tree trajectories

I am looking for help:
Beginning with a single node ($\circ$), at each discrete time step I can add a node/link pair to any node currently in the tree. Nodes are unlabelled and the tree is ...

**7**

votes

**0**answers

134 views

### Has anyone seen these binary trees (Catalan-type related to the Gegenbauer polynomials and Motzkin paths)?

The OEIS entry A121448 enumerates binary trees with $n$ edges and $k$ vertices with outdegree 1.
Has anyone seen these trees?
The o.g.f. for this entry, $G(x,t)$, is essentially a discriminant ...

**6**

votes

**1**answer

153 views

### Example to $2^\kappa\nrightarrow (3)^2_\kappa$, plus closed walks of odd length?

Let $\kappa$ be an infinite cardinal. Consider the following example to $2^\kappa\nrightarrow (3)^2_\kappa$.
$V$ is a set of vertices, each of which is an element of $2^\kappa$. Color the edge ...

**14**

votes

**1**answer

1k views

### Is deciding if one planar graph is dual to another really NP-hard (Wikipedia claim)?

Wikipedia claims (permanent link) without reference:
Testing whether one planar graph is dual to another is NP-complete.
Another claim with reference:
For any plane graph G, the medial graph ...

**1**

vote

**0**answers

56 views

### Mapping a grayscale image into a weighted undirected graph

I am looking for a method to convert an image into a network.
I have found the study Z. Wu, X. Lu, Y. Deng, Image edge detection
based on local dimension: A complex networks approach. Physica A
...

**2**

votes

**0**answers

97 views

### Systematic treatment of folding and valued graphs

I'm going to say beforehand that this question has something of a "am I missing something?" flavor. I'm in that odd position mathematicians often find themselves, where a topic has been addressed ...

**11**

votes

**2**answers

462 views

### Blinking graphs

For any simple graph $G$, assign its nodes a weight/bit of $0$ or $1$.
Call this a bit assignment for $G$.
Now, generate a new bit assignment as follows:
Each node $x$'s bit is replaced by $1$ if the ...

**6**

votes

**3**answers

243 views

### Numerical invariants for a graph or its complement that are bounded by some constant

I'm looking for numerical graph invariants that are bounded by a constant either for a graph $G$ or its complement $\bar{G}$. (The complement graph $\bar{G}$ has the same set of vertices as $G$ but ...