# Tagged Questions

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

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 ...
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 [...
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 ...
86 views

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 ...
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$ ...
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-...
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 ...
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. ...
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 ...
85 views

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