Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange
Join us in building a kind, collaborative learning community via our updated Code of Conduct.

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

1
vote
0answers
26 views

Halin Graphs with Highest Number of Hamilton Cycles

Halin graphs contain a Hamilton cycle and have the interesting property, that the shortest of all contained Hamilton cycles can be calculated in $O(n)$ time ("G. Cornuejols, D. Naddef, and W.R. ...
12
votes
2answers
220 views

Can we realize a graph as the skeleton of a polytope that has the same symmetries?

Given a graph $G$, a realization of $G$ as a polytope is a convex polytope $P\subseteq \Bbb R^n$ with $G$ as its 1-skeleton. A realization $P\subseteq \Bbb R^n$ is said to realize the symmetries of $...
4
votes
1answer
79 views

Two disjoint trees

Let $G$ be a graph and let $A_1, A_2 \subseteq V(G)$ be disjoint sets of vertices. Let us call $(A_1, A_2)$ independent if there exist vertex-disjoint trees $T_1, T_2 \subseteq G$ within $G$ which ...
0
votes
0answers
12 views

Name for Spanning Trees Containing all Edges of a Minimum Weight Perfect Matching

This question is motivated by the task of "uniformly" bicoloring the vertices of a symmetric TSP-instance graph with $2n$ vertices. A simple heuristical requirement for such a bicoloring could be ...
4
votes
0answers
35 views

Partitioning the vertices of a graph into induced trees

I am looking for previous work regarding graphs whose vertices can be assigned colours (not necessarily a proper colouring) in such a way that each colour class induces a tree. In particular I am ...
1
vote
0answers
16 views

The number of Laplacian eigenvalues of a graph in interval [k,n]

There are several upper and lower bounds for $m_G[2,n]$ (the number of Laplacian eigenvalues of a graph $G$ with $n$ vertices in the interval $[2,n]$). I want to know whether there exists any bound ...
5
votes
1answer
116 views

Counting promenades on graphs

Let a "promenade" on a tree be a walk going through every edge of the tree at least once, and such that the starting point and endpoint of the walk are distinct. What we mean by isomorphic promenades ...
1
vote
0answers
41 views

Matchings in infinite, not necessarily bipartite, graphs

Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs. Is there a similar generalization of Tutte's theorem on ...
5
votes
1answer
122 views

Why is the number of Perfect Matchings in a triangular grid equivalent to the number of Royal Paths?

The sequence A006318 at OEIS stands for the Schröder numbers. They describes the number of lattice paths from the southwest corner $(0,0)$ of an $n\times n$ grid to the northeast corner $(n,n)$, ...
6
votes
1answer
132 views

Smallest set of nonzero vectors in $\mathbb F_2^n$ which intersects every 2-dimensional subspace

What is the smallest set of nonzero vectors in $\mathbb F_2^n$ which intersects every 2-dimensional subspace? For example, for n = 3, the set {001, 010, 011} does the job, and is minimal. For n = 4, {...
2
votes
2answers
150 views

Random walk and isoperimetric constant

I assume that a result of the following kind is known, and I would really appreciate a reference for it... Or at least, some hints as to where to start looking. Theorem(?): Let $\varepsilon>0$ ...
1
vote
1answer
92 views

A weaker version of Dirac's theorem

This is related to Dirac's theorem. For any finite, simple, undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimal degree of all vertices. Are there positive integers $n,c\in\mathbb{N}$ with ...
4
votes
1answer
93 views

Can the bramble number and the strict bramble number of a graph be equal?

Let $G$ be a connected graph with vertices $V(G)$. A bramble of $G$ is a set of connected subgraphs $H_1,\ldots,H_n$ such that for each $i$ and $j$, $H_i$ touches $H_j$; that is, either $H_i$ ...
3
votes
0answers
63 views

Hadwiger number of Erdös-Faber-Lovasz graphs

For any set $X$, let $[X]^2 = \big\{\{a,b\}:a,b \in X, a\neq b\big\}$. We call a finite, simple, undirected graph $G=(V,E)$ an $n$-Erdös-Faber-Lovasz (EFL-) graph if there are $n$ subsets $S_1,\...
32
votes
2answers
3k views

How to find Erdős' treasure trove?

The renowned mathematician, Paul Erdős, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...
5
votes
1answer
142 views

“König's theorem” for $T_2$-spaces?

For any topological space $(X,\tau)$ we define a matching to be a collection of non-empty and pairwise disjoint open sets. We define the matching number $\nu(X,\tau)$ to be the smallest cardinal $\...
2
votes
0answers
31 views

Can Orientability of Manifolds be Generalized to TSP Instances?

It is well known, that there are two basic kinds of manifolds, orientable and non-orientable ones; the most simple examples being obtained by identifying a pair of opposite sides of a rectangular ...
4
votes
1answer
203 views

Cayley graph properties

Consider an infinite graph that satisfies the following property: if any finite set of vertices is removed (and all the adjacent edges), then the resulting graph has only one infinite connected ...
0
votes
0answers
21 views

Why do middle roots of the $\chi(p)$ graphs and percolation thresholds vary linearly with diagonal probability $q$ (in large random binary matrices)?

Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
2
votes
1answer
66 views

Generalization: (The “number” of) smaller sized clusters in large random binary matrices follow a descending order. Why?

This is a sequel to the question: Why is number of single cell clusters always greatest in a random matrix? In their answer, @Aaron Meyerowitz came up with a nice strategy to prove why the number of ...
3
votes
1answer
117 views

Why is number of single cell clusters always greatest in a random matrix?

Consider a large $N\times N$ square lattice, where each cell has a probability $p$ of being "occupied" (let's call denote them as "black") and a probability $1-p$ of being empty (let's denote them as "...
-2
votes
0answers
91 views

Help with graph theory

Is there any code that can calculate or a list of already calculated all homomorphic images of a graph or all $k$-chromatic ($k=4$ in particular) graphs with given number of vertices. I am interested ...
8
votes
2answers
197 views

Counting Hamiltonian cycles in $n \times n$ square grid

I wonder if anyone has counted these curves, either exactly or asymptotically? Let $S_n$ be an $n \times n$ subset of $\mathbb{Z}^2$ consisting of $n^2$ lattice points: a lattice square. Define a ...
2
votes
1answer
67 views

Is a simple graph matrix the sum of a “shiftordered” matrix and its transposed matrix

This is the generalization of a question Is a simple graph the "sum" of a partial order and its dual? Nik Weaver found a counterexample in a very nice, complete (and instantaneous!) answer,...
4
votes
2answers
303 views

Is a simple graph the “sum” of a partial order and its dual?

A "$n$-order matrix" $T\in M_n(\mathbb F_2)$ is a matrix such that there exists a partial ordered relation $\leq_T\subset [1,n]^2$ such that : $T_{ij}=1\Leftrightarrow i\leq_T j$ (where $T_{ij}$ is ...
1
vote
2answers
158 views

Bipartite subgraphs with lots of edges

Suppose $G=(V,E)$ is a simple, undirected graph with $|V|,|E|$ infinite. Is there $B\subseteq E$ with $|B| = |E|$ such that $(V,B)$ is bipartite?
2
votes
1answer
71 views

Concentration of measure in graph theory

I am looking for elementary statements in graph theory that illustrate the concentration of measure phenomenon. (Say, something bit more interesting than most of graphs have diameter 2.)
1
vote
0answers
66 views

Can we efficiently count modulo 2 the number of connected subgraphs of a planar graph?

Paper p.9 and Wikipedia relate the Tutte polynomial of a graph to another polynomial. If $(x-1)(y-1)=z$, $$T(G;x,y)=F_G(z,y)/H(G)$$ Where $F_G(z,y)=\sum_{A \subseteq E}z^{c(G_A)}(y-1)^{|A|} $ where ...
2
votes
1answer
78 views

Local-Global Principle in Graph Spectrum

The question is a bit vague, but any ideas/directions will be appreciated. Let us fix an $n$-vertex $d$-regular graph $G=(V,E)$. As I understand it, the eigenvalues of the adjacency matrix $A$ of $G$ ...
2
votes
1answer
157 views

Infinite graph with lots of non-isomorphic induced subgraphs

Given an infinite cardinal $\kappa$, is there a graph on $\kappa$ vertices that contains $2^\kappa$ pairwise non-isomorphic induced subgraphs?
5
votes
1answer
114 views

Domination numbers of infinite graphs

I got stuck on the following problem while thinking about this question. Let $G$ be an infinite graph. Say that a set of vertices $S$ of $G$ has a dominating pair if there exist $v,w \in S$ such that ...
2
votes
0answers
53 views

Reference request: Bipartite symmetric graphs are hamiltonian

Does anyone know whether bipartite symmetric graphs are hamiltonian? I'm not sure whether anyone have proved it before, but a nonhamiltonian symmetric bipartite graph would lead to a counterexample to ...
8
votes
1answer
372 views

Does Vizing's conjecture hold for the infinite graphs?

In finite graph theory, there are many (in)equalities which relate the integer value of a certain graph invariant (e.g. domination or chromatic number) for the product of two finite graphs (e.g. ...
9
votes
1answer
247 views

Finite group representation as $\mathrm{Aut}(\Gamma)$ action $H^1(\Gamma,\mathbb{Z})$ of graph?

Let $\Gamma$ be a finite graph, then $H^1(\Gamma,\mathbb{Z})\cong \mathbb{Z}^{g(\Gamma)}$ can be viewed as a $\mathrm{Aut}(\Gamma)$ module. Conversely, given a finite group $G$, and a $G$-module $\...
0
votes
0answers
41 views

Hopcroft-Karp Algorithm

I'm studying Hopcroft-Karp algorithm in bipartite graph. I can understand the theorems about the algorithm, but I want to find a more specific example. Can I find a bipartite graph that iterates an ...
3
votes
2answers
83 views

Is there an efficient way to represent all non-simple cycles of a digraph up to the number of vertices?

Given two digraphs $G$ and $H$, I want a method for creating a bijection between all non-simple cycles of for all $n \le |V(G)|$. That means, given $C_G(n)$ and $C_H(n)$ being the sets of all non-...
15
votes
1answer
231 views

Chromatic numbers of infinite abelian Cayley graphs

The recent striking progress on the chromatic number of the plane by de Grey arises from the interesting fact that certain Cayley graphs have large chromatic number; namely, the graph whose vertices ...
3
votes
1answer
79 views

Inertial decomposition of graphs

The problem is this: given a graph $G$, to find a decomposition of $G$, i.e. a set $F$ of vertex-disjoint proper subgraphs of $G$ such that: $$\text{inertia}(G) = \sum_{H \in F} \operatorname{...
1
vote
1answer
51 views

Infinite connected $k$-regular graphs

Is it true that for any integer $k\geq 3$ there are $\aleph_0$ many connected countably infinite, pairwise non-isomorphic $k$-regular graphs?
3
votes
2answers
99 views

Distance regular Cayley graphs on $Z_2^n$?

Let $Z_2^n$ be group $Z_2 \times Z_2 \times \cdots \times Z_2$ with operation Exclusive-or. I'd like to know if the $Cay(Z_2^n,S)$ for $S \subset Z_2^n \setminus \{0\}$ is distance regular graph or ...
0
votes
0answers
38 views

Edge coloring, with a special condition

I have a problem I am working on that can be reduced to the following case of edge coloring with a special condition. Let $G$ be a directed graph with infinite vertices that are colored with $m$ ...
1
vote
1answer
80 views

Infinite connected graphs isomorphic to their line graph

For any simple, undirected graph $G$, let $L(G)$ denote its line graph. $G=(\mathbb{Z}, E)$ with $E = \{\{k, k+1\}:k\in \mathbb{Z}\}$ has the property that $G\cong L(G)$. Is there a connected ...
15
votes
2answers
197 views

Labeling binary trees so that adjacent vertices differ by a power of two

Let $T$ be a finite rooted binary tree (where "binary tree" means that each node has at most two children, possibly less) with $n$ nodes in total. Is there a labeling of the nodes of $T$ with the ...
3
votes
2answers
222 views

Orientability of $\mathbb{Z}^n$

For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are ...
1
vote
0answers
36 views

$\exp(-Cn^{\epsilon})$ estimate for probability of Brouwer-Haemers condition in Erdos-Renyi-like random graph

For any $n$-vertex graph $G$, we have the inequality $\lambda_i^{L_G}\geq D_i-i+2,$ where $L_G$ denotes the Laplacian of $G$ and $\lambda_i^{L_G}$ denotes the $i^\text{th}$ largest eigenvalue and $D_i$...
2
votes
1answer
124 views

When does a row standardized adjacency matrix have a real spectrum?

A colleague in spatial statistics was looking at a map with about 600 regions. For the application she's considering, the induced adjacency matrix had some undesirable properties (where two regions ...
1
vote
0answers
86 views

Characterization of k-walk-equivalent graphs

Let $G=(V,E)$ be an undirected graph. A walk of length $k$ in $G$ is a sequence of vertices $v_1,v_2,\ldots,v_{k+1}$ in $V$ such that $(v_i,v_{i+1})\in E$ for each $i=1,2,\ldots,k$. Call two graphs $...
2
votes
0answers
36 views

On the frequency with which a vertex can be added to the independent sets in a graph

Let $i(G)$ denote the number of independent sets of vertices of a graph $G$, write $G-v$ for the graph $G$ with the vertex $v$ removed, $G-H$ for the graph $G$ with the subgraph $H$ removed, and $N_k(...
2
votes
1answer
97 views

$\omega$-Hamilton paths in $\mathbb{Z}^n$

For any set $X$ set $[X]^2 = \{\{x,y\}: x,y\in X, x\neq y\}$. If $n\geq 2$ is an integer, we endow $\mathbb{Z}$ with a graph structure in the following way. If $x,y\in \mathbb{Z}^n$ we say $x,y$ are ...
6
votes
1answer
232 views

A permutation problem

Here I ask a question on permutations of $n$ distinct real numbers. QUESTION: Let $a_1,a_2,\ldots,a_n\ (n>1)$ be (pairwise) distinct real numbers. Is there a permutation $b_1,\ldots,b_n$ of $a_1,\...