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

Questions tagged [graph-theory]

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, topological-graph-theory, random-graphs, graph-colorings and several others.

2
votes
1answer
163 views

Asking for an example of a graph $G$ satisfying the following property

This question comes from another question I submitted earlier. Let $G$ be a finite graph. For any independent set $S$ in $G$ with $|S|\geqslant2$ and $v\in S$, define $$d_S(v)=\mid\{u\in V(G)\...
4
votes
1answer
147 views

The existence of a specific kind of independent set in a connected graph satisfying the following property

Suppose $G$ is a connected finite graph satisfying that every edge $uv$ of $G$ belongs to a "triangle" $uvw$ such that $uv,uw\in E(G),\ vw\notin E(G)$ or $uv,vw\in E(G),\ uw\notin E(G)$(in other words,...
7
votes
1answer
139 views

Grinberg's uniquely hamiltonian 3-connected graphs (Russian paper)

Many years ago, Grinberg found some uniquely-hamiltonian $3$-connected graphs, and published his results in a paper that has been cited several times as follows. E. Grinberg, Three-connected graphs ...
1
vote
0answers
17 views

Complex of graphs with domination number greater than k

I am studying discrete Morse theory and as an example, discrete Morse theory is used to obtain the homotopy type of the complex of non-connected graphs of $n$ vertices. I also read that this kind of ...
1
vote
0answers
64 views

Percolation and diameter of graph

Is the critical probability in percolation and diameter of graph related. I guess larger the diameter higher the probability. Is there any result like this? By critical probability I mean the ...
1
vote
1answer
104 views

Walks of odd Lengths in a Matrix

Consider the following matrix $$ A=\left[ \begin {array}{cccc} 1&1&0&0\\ 0&0&1&0\\ 0&0&1&1\\ 1&0&0&0 \end {array} \right]. $$ Assume that $B=A^k$ ...
0
votes
1answer
55 views

Standard names of two finitary properties of hypergraphs?

Now we are writing a paper on minimal covers and minimal vertex-covers in hypergraphs and would like to know if there are any standard names for the following two (dual) properties of a hypergraph $(V,...
12
votes
1answer
380 views

Is each cover of the plane by lines minimizable?

A cover $\mathcal C$ of a set $X$ by subsets of $X$ is called $\bullet$ minimal if for every $C\in\mathcal C$ the family $\mathcal C\setminus\{C\}$ is not a cover of $X$; $\bullet$ minimizable if $\...
1
vote
1answer
42 views

Optimal Graph Splitting

Question: Given a finite symmetric TSP instance with $2n$ sites, what is the complexity of and what are algorithms for determining two sets of sites $A$ and $B$, each containing $n$ elemenents so that ...
3
votes
0answers
107 views

Halin Graphs with Highest Number of Hamilton Cycles

Halin graphs contain a Hamilton cycle and have the interesting property, that, also in the case of arbitrary real edge weights, it is possible to report one of the shortest contained Hamilton cycles ...
15
votes
3answers
433 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 $...
7
votes
1answer
109 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
14 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 ...
7
votes
0answers
69 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
32 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
181 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
56 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
149 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
141 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
169 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
103 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
97 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
103 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,\...
34
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
151 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
32 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 ...
5
votes
1answer
232 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
71 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
134 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 "...
9
votes
2answers
245 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
77 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
3answers
335 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
167 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?
3
votes
1answer
92 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
69 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
85 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$ ...
3
votes
1answer
166 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
122 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 ...
3
votes
0answers
64 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
384 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
250 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
53 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 ...
4
votes
2answers
88 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
277 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
97 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
62 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
109 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
43 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
83 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 ...