Questions about the branch of combinatorics called graph theory (not to be used for questions concerning the graph of a function). This tag can be further specialized via using it in combination with more specialized tags such as extremal-graph-theory, spectral-graph-theory, algebraic-graph-theory, ...

learn more… | top users | synonyms

2
votes
1answer
144 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
0answers
26 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
0answers
107 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 X\to\...
0
votes
1answer
93 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 } i\in\{1,2\}\...
0
votes
0answers
36 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 nonnegative ...
0
votes
0answers
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
1answer
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
0answers
47 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
0answers
90 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
0answers
135 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
1answer
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
1answer
69 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
1answer
40 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 ...
1
vote
1answer
174 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
1answer
145 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
2answers
100 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
0answers
49 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
1answer
77 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
3answers
89 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
0answers
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
1answer
136 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
2answers
175 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
1answer
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 $(1,...
2
votes
1answer
70 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
0answers
65 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
2answers
362 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
1answer
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
0answers
66 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
0answers
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
0answers
50 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 tree-...
4
votes
2answers
206 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
1answer
234 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
1answer
157 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
2answers
86 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
1answer
83 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
0answers
85 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 ...
6
votes
1answer
170 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
0answers
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
1answer
98 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
1answer
176 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
0answers
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
2answers
252 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
0answers
45 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
1answer
323 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
0answers
63 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
1answer
140 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
0answers
135 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
1answer
154 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
1answer
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
0answers
63 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 (2015),...