# Tagged Questions

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

127 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

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

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

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

62 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

361 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

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

**4**

votes

**2**answers

181 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

233 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

154 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

85 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

77 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

84 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

**1**answer

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

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

175 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

251 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

267 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

62 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

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

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

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

**3**

votes

**0**answers

98 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

465 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

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

**2**

votes

**1**answer

128 views

### Properties of bipartite graphs

For a connected bipartite graph $G$ are the two following properties equivalent:
1)Every minimal cycle in $G$ has length 4, that is every cycle of length strictly greater than 4 can be divided in ...

**22**

votes

**10**answers

1k views

### What (fun) results in graph theory should undergraduates learn?

I have the task of creating a 3rd year undergraduate course in graph theory (in the UK). Essentially the students will have seen minimal discrete math/combinatorics before this course. Since graph ...

**8**

votes

**1**answer

121 views

### How many uniquely colored degree two vertices in 3-coloring of subcubic graph?

Is there a graph with maximum degree three that has 3 degree two vertices that must get the same (resp. different) color in every 3-coloring of the graph?
I'm interested in any similar results as ...

**0**

votes

**0**answers

38 views

### How does subdividing an edge change the Tutte polynomial of graph at $x=0$?

Let $T_G(x,y)$ be the Tutte polynomial of simple graph $G$.
Let $G'$ be $G$ with an edge subdivided (choose any edge).
Limited experiments suggest:
Conjecture 1: $T_G(0,y)=T_{G'}(0,y)$.
Is ...

**2**

votes

**1**answer

69 views

### Induced matching of cycle

Definition:
A graph $G$ is chordal if every induced cycle in $G$ has length 3, and is co-chordal if the complement graph $G^c$ is chordal.The co-chordal
cover number, denoted $cochord (G)$, is the ...

**1**

vote

**1**answer

83 views

### Vectors which average to zero over any graph neighborhood

Given an undirected connected graph on $n$ nodes, let $S$ be the subspace of vectors $x \in \mathbb{R}^n$ which satisfy $$\sum_{j \in N(i)} x_j = 0,$$ for all $i=1, \ldots, n$. Here $N(i)$ is the set ...

**1**

vote

**2**answers

58 views

### Maximal Minimum Weight DAGs

In the case of undirected, connected graphs the name for the maximal cycle-free subgraph of minimal weight is called Minimum Spanning Tree, and the efficient algorithms for their calculation are well ...

**1**

vote

**0**answers

65 views

### A property of minimal prime ideals in rings with finite chromatic number

Let $R$ be a commutative ring with identity. There are so many ways to associate a graph to $R$. Consider this: take the elements of $R$ (All elements including zero) as vertices an two distinct ...

**3**

votes

**1**answer

61 views

### Complexity of counting MAXCUT in planar graphs — seemingly contradicting claims

Confusion is likely. Appears to me two papers give contradicting claims
about the complexity of counting MAXCUT in planar graphs.
Exact Max 2-SAT: Easier and Faster p. 6
However, counting the ...

**1**

vote

**0**answers

53 views

### Directed graph Laplacian with exactly one negative eigenvalue

Let $G$ be a digraph with adjacency matrix $A =(A_{ij})$ where $A_{ij}=1$ if and only if there is a directed edge $i \to j$ and $A_{ij}=0$ otherwise. Let $D= (D_{ij})$ be the degree matrix with $D_{ij}...

**5**

votes

**1**answer

92 views

### Characterization of non-isomorphic graphs but isomorphic total graphs?

Given a graph $G$, the total graph of $G$, denoted $T(G)$, is the graph with vertex set $V(G) \cup E(G)$, where $a$ and $b$ are adjacent in $T(G)$ if and only if they are adjacent or incident in $G$. ...

**0**

votes

**0**answers

32 views

### Linear Program for Single Source Shortest Paths Tree

This question originates in quick, however wrong, idea to calculate a shortest paths tree in the presence of negative cycles. The essential motivation was that a linear program would determine binary ...

**4**

votes

**1**answer

146 views

### Probability bound for perfect matching

Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...

**2**

votes

**1**answer

85 views

### Spectrum of Laplacian matrix of an infinite tree graph

I'm having difficulty understanding a fact stated in a research paper I'm reading. Namely, let $T$ be a tree with all nodes of degree $4$ (ie, the root has $4$ daughter nodes and all other nodes have $...

**2**

votes

**1**answer

164 views

### Extracting a full rank matrix from a 0-1 matrix

If $A$ is a $n\!\times\!n$ $0$-$1$ matrix of rank $k<n$. If ever possible, what would be an efficient way of extracting a full rank $k\!\times\!k$ sub-matrix of $A$ by removing columns and rows of ...

**3**

votes

**1**answer

77 views

### Generalizations of the Triangle Removal Lemma to smaller exponents

The Triangle Removal Lemma states:
For all $\epsilon > 0$, there is a $\delta > 0$ such that any graph on $n$ vertices with at most $\delta n^3$ triangles may be made triangle-free by ...