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.

6
votes
0answers
180 views

$R(3,6) = 18$, especially proving that $R(3,6)>17$

I'm studying the Ramsey numbers, especially $R(3,6) = 18$ I understand that the proof using the theorem $R(m,n) <R(m-1,n)+R(m,n-1)$ can only prove that $R(3,6)<20$. However by Cariolaro's "On ...
19
votes
3answers
806 views

Does the hypergraph of subgroups determine a group?

A hypergraph is a pair $H=(V,E)$ where $V\neq \emptyset$ is a set and $E\subseteq{\cal P}(V)$ is a collection of subsets of $V$. We say two hypergraphs $H_i=(V_i, E_i)$ for $i=1,2$ are isomorphic if ...
6
votes
1answer
211 views

Blocking $a\to b\to c$ in a DAG with bounded degrees

(This is an (easy-looking) toy question for this one.) Question. Find the smallest $\alpha$ satisfying the following: Let $G=(V,E)$ be a finite directed acyclic graph, where each in- and out-...
12
votes
3answers
498 views

A Modern Proof of Erdos and Renyi's 1959 Random Graph Paper?

In their paper, Erdos and Renyi consider a random graph with a fixed number of edges, as opposed to the more modern approach of adding each edge independently with probability $p$. From what I ...
1
vote
1answer
68 views

$(k,n)$-binary graphs

Let $k\leq n$ be positive integers with $n\geq 2$, and let $[n]=\{1,\ldots,n\}$. Let $V_n=\{0,1\}^{[n]}$ be the set of all functions $f:[n]\to\{0,1\}$, and let $$E_{k,n} =\big\{\{f,g\}: f,g\in V_n\...
13
votes
1answer
276 views

Can the graph of a symmetric polytope have more symmetries than the polytope itself?

I consider convex polytopes $P\subseteq\Bbb R^d$ (convex hull of finitely many points) which are arc-transitive, i.e. where the automorphism group acts transitively on the 1-flags (incident vertex-...
9
votes
1answer
194 views

Representations of the automorphism group of graphs via spectral graphs theory

Given a (simple) graph $G=(V,E)$ with $V=\{1,...,n\}$ and let $A$ be its adjacency matrix. I am interested in the representation theory (over $\Bbb R$) of the automorphism group $\def\Aut{\mathrm{Aut}...
19
votes
2answers
977 views

Is it possible that both a graph and its complement have small connectivity?

Let $G=(V,E)$ be a simple graph with $n$ vertices. The isoperimetric constant of $G$ is defined as $$ i(G) := \min_{A \subset V,|A| \leq \frac n2} \frac{|\partial A|}{|A|} $$ where $\partial A$ is ...
1
vote
1answer
62 views

The Kronecker product of two bipartite graphs' biadjacency matrices: what's it called?

Here's two random $(0,1)$-matrices: $$ A= \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 1 \\ \end{bmatrix} \qquad B= \begin{bmatrix} 1 & 1 \\ 0 & 1 \\ \end{bmatrix}. $$ They can be ...
6
votes
0answers
81 views

Combinatorial region-halfplane incidence structures

I've seen a bunch of similar MO questions, yet hopefully this is not a complete duplicate. Consider $n$ halfplanes in $\mathbb{R}^2$ with their borders in general position, that is, no point of $\...
2
votes
0answers
125 views

Space of change of basis matrices between two similar matrices - how to reduce it with additional tests?

Assume we have two real symmetric $n\times n$ matrices: $A, B$. We can easily test their similarity: $\textrm{Tr}(A^k)=\textrm{Tr}(B^k)$ for $k=1..n$. In this case both can be rotated to the same ...
1
vote
0answers
51 views

A Random Graph Process

I'd like to understand the following random graph process. I'm not sure if it's difficult or straightforward, so apologies if this is below the level of mathoverflow, but I've gotten no response on ...
-1
votes
1answer
37 views

pruning a special graph

You are given a very special graph. The vertices of the graph come in three columns: left, center, and right. The edges connect vertices from the left to vertices in the center, and from the center to ...
0
votes
0answers
18 views

When is the first blocking flow created in Dinic's algorithm a max flow?

When is the first blocking flow created in Dinic's algorithm a max flow? I understand that this is usually an iterated algorithm where one creates level graphs and augments the existing blocking flow ...
8
votes
0answers
349 views

Colored weighted Graphs with only monochromatic perfect matchings

The following purely graph-theoretic question is motivated by quantum mechanics. Definitions: A bi-colored weighted graph $G(V,E)$ is an undirected graph where every edge is colored, and has a ...
2
votes
1answer
128 views

Graphs with exactly $n$ perfect matchings

Is there for every $n\in\mathbb{N}$ a connected, simple, undirected graph $G_n=(V_n,E_n)$ such that $G_n$ has exactly $n$ perfect matchings?
6
votes
0answers
131 views

What is known about the distribution of lengths of the cycle you get by adding an edge to a uniform spanning tree?

Let $G$ be a finite, connected graph. Let $T$ be a uniform spanning tree, and let $e$ be a uniformly random edge not in $T$. When we add $e$ to $T$, we get a subgraph with a unique cycle, $C$. I am ...
0
votes
1answer
81 views

Connected infinite graphs in which all matchings are “small”

Is there a countable, simple, connected graph $G=(\omega, E)$ such that $\text{deg}(v)$ is infinite for all $v\in \omega$, and for all matchings $M\subseteq E$ the set $V\setminus (\bigcup M)$ is ...
5
votes
1answer
103 views

Two graphs with the same number of walks but without a common equitable partition

Consider two undirected graphs $G$ and $H$ of the same order (same number of vertices). If $G$ and $H$ have a common equitable partition, then it is known (see e.g., Chapter 6 in 1) that these ...
3
votes
1answer
100 views

Asymptotic colouring of edges and vertices, and untwisting cocycles

This question regards colourings on edges and vertices on countable directed multigraphs. We start with an example. Let $G=\mathbb Z^2$. We define two functions $a_h$ and $a_v$ from $\mathbb Z^2$ to $\...
1
vote
1answer
54 views

monochromatic induced subgraph in a complete 3-partite graph

$H=(V_1\cup V_2 \cup V_3, E)$ is a complete $3$ partite graph such that $|V_1|=|V_2|=|V_3|=n$ . Color the edges with three colors. My question is: Is it possible to find sets $V_1' \subset V_1, V_2' ...
0
votes
0answers
72 views

A series of operations on a graph $G$ to obtain a specific family of subgraphs of $G$

Suppose $G$ is the complete graph on $n$ vertices, do the following operations: Let $G_0=G$. Choose one vertex of $G_0$ and let $G_1$ be the subgraph of $G_0$ by taking this vertex away from $G_0$. ...
3
votes
1answer
74 views

Maximal matchings in connected graphs

Let $n\in\mathbb{N}$ be a positive integer. Is there a connected graph $G$ such that $G$ cannot be coloured with less than $n$ colours, and every two maximal matchings have non-empty intersection? (I ...
2
votes
2answers
102 views

Graphs in which all maximal matchings intersect

Let $G=(V,E)$ be a simple, undirected graph. A matching is a set $M\subseteq E$ consisting of pairwise disjoint edges. We say $M$ is maximal if it is maximal amongst all matchings in $G$ with respect ...
0
votes
0answers
25 views

Search an undirected graph for a path with specified, ordered vertex valencies

Consider an arbitrary finite undirected graph $G = (V,E)$ and a specified finite sequence of vertex valencies or degrees, $\{ d_1, d_2, \ldots d_k\}$, where $k \le O(G)$ (the order of $G$). Is there ...
4
votes
1answer
320 views

Mathematical Structure and Objects Induced by Pairs of Disjoint Subsets

Let $\mathcal{S}$ be a finite, discrete and non-empty set, i.e., $$\begin{align} \operatorname{card}\left(\mathcal{S}\right) & =:n\in\mathbb{N}^+\\ V& :=\{v\subset\mathcal{S}\ |\ v\ne\...
7
votes
1answer
256 views

Number of (distinct) knots with a bounded number of crossings

The title pretty much covers it: are there good (asymptotic) estimates on the number of knot types whose projection has at most $N$ crossings? Similar question with "projection" replaced by "...
0
votes
3answers
85 views

Minimize edge number under diameter and max-degree constraint

Given a number n of nodes, a diameter d (d>1) and a max-degree k. Let's assume d and k are chosen such that a graph with n nodes with the desired diameter and max-degree exists. What is the minimum ...
0
votes
1answer
96 views

Find all paths on undirected Graph [closed]

I have an undirected graph and i want to list all possible paths from a starting node. Each connection between 2 nodes is unique in a listed path is unique, for example give this graph representation:...
4
votes
2answers
55 views

Vertex cover number vs matching number

Let $G=(V,E)$ be a finite, simple, undirected graph. A matching is a set $M\subseteq E$ of pairwise disjoint edges. A vertex cover is a set $C\subseteq V$ of vertices such that $C\cap e \neq \emptyset$...
3
votes
0answers
101 views

$\mathrm{NP}$-complete problems in graph theory: undirected vs. directed

Is it true that it is much easier to establish $\mathrm{NP}$-complete on undirected graphs than digraphs (directed graph)? Academic articles proving $\mathrm{NP}$-completeness of problems on ...
4
votes
0answers
133 views

Groups inducing edge-colorings on graphs. Is this concept known?

Are the following concepts known in graph/group theory, and if Yes, what are they called and where to read about them? Because I do not know better, I gave them placeholder names for now. 1. ...
1
vote
2answers
100 views

Constructing an n-node DAG, with exactly k paths between node 1 and node n [closed]

Pretty straight forward, yet I didn't find how to approach such a problem. I tried constructing a solution from the reverse problem (Given a DAG count the number of paths between node 1 and node n), ...
2
votes
0answers
67 views

Tutte polynomial from independent sets of a graph

Let $G$ be a connected graph with chromatic polynomial $X(G,q)$. Since $k$-proper coloring a graph is same as partitioning the vertex set $V$ into $k$ independent sets (a subset of the vertex set in ...
0
votes
1answer
201 views

How to find a random cycle in a large graph?

Suppose we have a large directed graph $G$ with no self-cycle and no more than one edge between two nodes, for example, containing about 2000 nodes and about 10 edges per node. Now we need to achieve ...
7
votes
0answers
133 views

IH-moves on trivalent graphs, and a complex that might be known to low-dimensional topologists

Here is a combinatorial problem which is hard to Google but seems like it might have a solution well known to people who study finite type invariants etc. Let $G_{g,b}$ denote the set of finite ...
5
votes
1answer
161 views

$\{ P_3, P_4 \}$-factor

Definition. A graph $G=(V,E)$ is to be $\{d_1,\dots,d_n\}$-graph if for each vertex $v\in V$ we have $\text{deg}(v)=d_i$ for some $i=1,\dots n$. Definition. A connected graph $G=(V,E)$ is called $...
6
votes
1answer
221 views

Which zero-diagonal matrices contain the all-one vector in their columns' conic hull?

Let $A$ be a non-negative zero-diagonal invertible matrix. Which $A$ make the following assertions true, which are all equivalent: The all-one vector $j$ is contained in the conic hull of $col(A)$. ...
5
votes
1answer
330 views

Countable version of Erdös-Lovasz-Faber conjecture

Let $X$ be an infinite set, and let $(A_n)_{n\in\omega}$ be a collection of subsets of $X$ with the following properties: $|A_m\cap A_n| \leq 1$ for $m\neq n\in \omega$, and $|A_n|=\aleph_0$ for all $...
5
votes
1answer
193 views

Can two non-equivalent polytopes of same dimension have the same graph?

By a polytope I mean the convex hull of finitely many points. The graph of a polytope is the graph isomorphic to its 1-skeleton. By equivalence of polytopes I mean combinatorial equivalence, i.e. ...
8
votes
1answer
178 views

Maximum number of triangles no two of which have a common edge

For $n\in N_+$, define f(n) to be that for any n-vertice graph G, if any two triangle in G don't have a common edge, then G has at most f(n) triangles. Do we have some good estimates for f(n)? By ...
3
votes
1answer
68 views

Transfer-impedance matrix for edge correlations in random spanning tree

Suppose $G$ is a (weighted) connected graph and let $T$ denote a random spanning tree of $G$, chosen uniformly (or respecting the edge weights). It is known that for any distinct edges $e, f$ $$\...
0
votes
0answers
47 views

Interesting First-Order Properties of Hypercubes and Grids

Hypercubes: The $n$-hypercube is the graph $H_n$ whose vertex set $V(H_n)$ consists of all binary string of length $n$, and the edges are pairs of the form $\{w,w'\}$ where $w$ and $w'$ differ in ...
4
votes
1answer
109 views

Increasing the chromatic number by “folding” two vertices of distance 2

Is there a finite, connected, simple, undirected graph $G=(V,E)$ such that $G$ is not complete, and whenever two vertices of distance $2$ are identified ("folded"), then the chromatic number ...
3
votes
0answers
64 views

Reconstructing plane graphs from degree- and face-sequences

Let $G$ be a plane $3$-connected graph; so it partitions the plane into regions bounded by faces. Let $\mathrm{deg}_v$ be the sequence of vertex degrees of $G$, and $\mathrm{deg}_f$ be the sequence of ...
4
votes
2answers
340 views

How many vertices can a self-complementary graph have?

Counting edges easily shows that if $n$ is congruent to 2 or 3 modulo 4, there is no self-complementary graph on $n$ vertices. Is the converse true? What I know: Paley graphs are self-complementary,...
2
votes
1answer
80 views

Compactness of Hadwiger number

Is there an infinite, simple, undirected graph $G=(V,E)$ such that there is $n\in\mathbb{N}$ with the following properties? $K_n$ is a minor of $G$, but $K_{n+1}$ is not a minor of $G$, and if $F$ ...
0
votes
0answers
33 views

Graph homomorphism from a high-girth graph to the sub-graph of a high-girth graph

Consider a classical result: There are degree-$d$ (appropriate random) graphs on $n$ vertices with girth $\Omega(\log n/\log d)$ of chromatic number $\Omega(d/\log d)$ for arbitrary large $n$. We can ...
2
votes
0answers
55 views

Distance-preserving graph contraction to a given set of vertices

I am trying to resolve the following problem and was wondering if there already exists consecrated algorithms to solve it. Let $G(V,E)$ be a weighted graph with vertices $V$ connected through ...
3
votes
0answers
116 views

Blocking directed paths on a DAG with a linear number of vertex defects

Let $G=(V,E)$ be a directed acyclic graph. Define the set of all directed paths in $G$ by $\Gamma$. Given a subset $W\subseteq V$, let $\Gamma_W\subseteq \Gamma$ be the set of all paths in $\Gamma$ ...