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

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
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
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
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
0answers
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
2answers
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
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
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
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
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
2answers
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
1answer
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
1answer
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
2answers
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
1answer
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
0answers
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
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
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
1answer
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
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
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
0answers
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
1answer
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
0answers
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
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
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
1answer
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
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),...
3
votes
0answers
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
2answers
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
3answers
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
1answer
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
10answers
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
1answer
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
0answers
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
1answer
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
1answer
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
2answers
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
0answers
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
1answer
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
0answers
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
1answer
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
0answers
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
1answer
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
1answer
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
1answer
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
1answer
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 ...