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.

Filter by
Sorted by
Tagged with
7
votes
0answers
65 views

Is every 1-million-connected graph rigid in 3D?

It is an old result that every $6$-connected graph is rigid in $\mathbb{R}^2$: Lovász, László, and Yechiam Yemini. "On generic rigidity in the plane." SIAM Journal on Algebraic Discrete ...
2
votes
1answer
39 views

Minimizing the degree of outgoing edges in a digraph, does this problem have a name?

I have a problem which can be rephrased in this way. Suppose $G = (V,E)$ is a digraph (directed graph) and for each $v \in V$ we denote with $\delta^+(v)$ the number of outgoing edges of the vertex $v$...
3
votes
1answer
188 views

Coloring almost-disjointness

Let $[\omega]^\omega$ denote the collection of infinite subsets of $\omega$. Let $$E = \big\{\{A,B\}: A,B \in [\omega]^\omega \text{ and } |A\cap B| \text{ is finite}\big\}.$$ We consider the graph $G=...
1
vote
0answers
40 views

Another betweenness centrality measure: neighbourhood centrality

Among the many centrality measures that I have heard of, I miss the following (but maybe I'm just blind). Consider a graph $G$ with $k$ connected components $G_i$ of size $|G_i|$. The number of node ...
4
votes
2answers
117 views

The number of monochromatic triangles

It is well known that the minimum number of monochromatic triangles in a red/blue coloring of the edges of the complete graph $K_n$ is given by Goodman's formula $$M(n)=\binom n3-\left\lfloor\frac n2\...
1
vote
1answer
60 views

Finite graph not embeddable in $H(n,2)$

Let $n\in\mathbb{N}$ and consider $x,y \in\{0,1\}^n$. The Hamming distance of $x,y$ is defined by $$d_H(x,y) = |\{i\in \{0,\ldots, n-1\}:x_i\neq y_i\}|.$$ For $n\geq 2$ let $H(n,2)$ be the graph given ...
1
vote
0answers
41 views

Is there any theorem similar to the Tutte–Berge formula?

Tutte–Berge formula is a characterization of the size of a maximum matching in a graph. The theorem states that the size of a maximum matching of a graph ${\displaystyle G=(V,E)}$ equals $${\...
9
votes
1answer
283 views
+100

Conjecture on minimum size of graph

Given a graph $G(V,E)$, let $\chi(G)$ be its chromatic number, and $\chi_1(G)$ its 1-improper chromatic number (meaning that each node can have at most 1 neighbor with the same color; or another way ...
0
votes
2answers
58 views

Acyclic proper coloring of 2-degenerate graphs

A proper vertex coloring of a graph $G$ is acyclic if there is no bicolored cycle. A graph is 2-degenerate if its every subgraph has a vertex of degree at most 2. I think every 2-degenerate graph has ...
0
votes
0answers
52 views

Possible trajectories with time travel [closed]

First of all, I'm not a mathematician, so sorry if the question is in layman terms. In the following picture, there is a character traveling to the right. If the character encounters another character,...
0
votes
1answer
76 views

Could you provide some TSP examples from real world to test a new algorithm?

It's well known that to find a hamilton cycle is NPC, while TSP is NPH. But it seems that for majority of graphs (density of edge > 0.1, order > 100) there is a fast algorithm to find different ...
2
votes
1answer
130 views

For a three-connected graph, is there a contraction edge that strictly increases vertex connectivity?

In graph theory, an edge contraction is an operation which removes an edge from a graph while simultaneously merging the two vertices that it previously joined. edge contraction As defined below, an ...
0
votes
0answers
32 views

Travelling salesman problem with variable weights

Take a fully connected graph with $v$ vertices. We assign weights to edges using an arbitrary function $f_{ij}(x)$ for pairs of vertices $0 < i, j \le v$, then starting at $c_{0}=0$, traverse the ...
6
votes
1answer
161 views

Determinant of walk matrix for a skew-symmetric matrix of even order

Let $S=(s_{ij})$ be a skew-symmetric integral matrix of order $n$. We only consider the case that $n$ is even. Let $e$ be the all-one vector in $\mathbb{R}^n$. Define the walk matrix $$W(S)=[e,Se,\...
4
votes
2answers
240 views

High degree differences in bipartite graphs

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us define the quantity: $$\mathcal{I}_k(G) := \sum_{1\le i,j \le n} \mathbb{1}{\Big\{|\mathrm{deg}(v_i)-\...
7
votes
1answer
199 views

Are two quasi-isometric, isomorphic on large enough balls, transitive graphs isomorphic?

Take two transitive graphs $X,Y$ (potentially directed and edge-labelled, e.g. Cayley graphs). Assume $X,Y$ are quasi-isometric with constant $K$, i.e. there exists a function $f:VX \to VY$ ($VX,\,VY$ ...
0
votes
0answers
89 views

How to classify rings by combinatorial structures?

There are many ways to encode information about algebraic structures such as groups, rings, etc... in combinatorial form. For example the Cayley graph of a group with a subset of generators, or the ...
11
votes
1answer
387 views

“Drinking number” of a graph

Motivation. A while ago I attended a party and I only knew some, but not all, of the attendees. There were 2 kinds of drinks: beer and soda. I noticed that amongst my acquaintances, more than half ...
8
votes
1answer
206 views

Find all Non-isomorphic good drawings of $K_{3,3}$?

Sometimes I look at all non-isomorphic good drawings of graphs on a plane or sphere. Good drawing means that no edge crosses itself, no two edges cross more than once, and no two edges incident with ...
2
votes
0answers
136 views

Random walk on non-abelian free group

Let $F_2$ be the free non-abelian group with generators $a, b\in F_2$. Has the "random walk" where we start with the identity and then multiply it by $a$ or $b$ or $a^{-1}$ or $b^{-1}$ ...
0
votes
0answers
43 views

Sufficient criterion for unit distance graphs

There are many necessary criteria for a graph to be a unit distance graph. For example, it must not have $K_4$ as a subgraph etc. Can we find some sufficient criterion for a graph to be a unit ...
3
votes
1answer
85 views

Constructing a 1-planar graph that has no rectilinear drawing

A 1-planar graph is a graph that can be drawn in the Euclidean plane in such a way that each edge has at most one crossing point, where it crosses a single additional edge. 1 planar graph I read the ...
2
votes
0answers
42 views

Coloring finite subsets of a fixed size with a single modular function

Let $k$ and $N$ be positive integers so that $k\mid N$. Let $M=(k/N){N\choose k}$. A function $f:[N]^k\rightarrow M$ is a coloring function if $f(s_1) = f(s_2)$ implies that $s_1=s_2$ or $s_1 \cap ...
-1
votes
1answer
141 views

Helsgaun's $k$-Opt moves

In his 2009 paper General k-opt submoves for the Lin–Kernighan TSP heuristic, Helsgaun defines the local tour improvements on which the LKH heuristics are based as: several questions arise from that ...
11
votes
2answers
777 views

How many finitely-generated-by-elements-of-finite-order-groups are there?

I do not know where this question is on the trivial to intractable spectrum. Consider the set of isomorphism classes of groups finitely generated by elements of finite order. What is the cardinality ...
1
vote
0answers
133 views

Is this graph theory paper in German translated into English?

I recently read such a paper and want to understand the proof idea of ​​this article. However since it is in German and I have not studied German before, I'd like to ask whether this paper has an ...
12
votes
1answer
409 views

Is the Petersen graph a “Cayley graph” of some more general group-like structure?

The Petersen graph is the smallest vertex-transitive graph which is not a Cayley graph. Is it the "Cayley graph" of some slightly more general group-like structure?
1
vote
1answer
89 views

Can Tutte embedding be guaranteed that each face is convex?

In graph drawing and geometric graph theory, a Tutte embedding of a simple 3-vertex-connected planar graph is a crossing-free straight-line embedding with the properties that the outer face is a ...
5
votes
2answers
220 views

Line graphs called “graph derivatives”: any intuition?

Short version: in several papers, line graphs (and closely related graphs) are called graph derivatives or derived graphs; is there any intuition for such terminologies, in connection with the ...
0
votes
0answers
16 views

Probability that edge exchange yields a tour

let $H$ be a Hamilton cycle in a complete topological symmetric graph $G$ of finite size. Question: what is the probability that a vertex-disjoint cycle cover $C_k$ that is generated from $H$ by ...
0
votes
0answers
42 views

maximum radius for a $k$-set of vertices in a graph

this is a cross-post from mse here. Let $G$ be a connected graph and $S$ a subset of its vertices. Given a vertex $v$ of $G$ we define the $S$-eccentricity of $v$ as the largest distance between $v$ ...
1
vote
0answers
63 views

Fastest algorithm to construct a proper edge $(\Delta(G)+1)$-coloring of a simple graph

A proper edge coloring is a coloring of the edges of a graph so that adjacent edges receive distinct colors. Vizing's theorem states that every simple graph $G$ has a proper edge coloring using at ...
1
vote
0answers
83 views

Probability that a graph and its complement are connected

It's well known that for any graph $G = (V,E)$ that if $G$ is not connected, then its compliment $\overline{G}$ is connected. So, it's impossible to have both $G$ and $\overline{G}$ be disconnected. ...
1
vote
0answers
77 views

When are the 3-colorings of vertex subsets uncorrelated?

Let $G=(V,E)$ be a simple, undirected, vertex 3-colourable graph, and call the set of its proper vertex 3-colourings $C$. For any subset of vertices, $A\subset V$, define $C_A$ as the set of distinct ...
1
vote
1answer
73 views

Probability process involving blocking paths of rooted tree

Consider a rooted tree $T$ and $n$ leaf nodes which are all at depth $R$. We would like to select a random subset $S$ of the edges of $T$, such that (i) Every root-leaf path of $T$ contains at least ...
9
votes
3answers
413 views

Pairs of vertices with high degree difference

Consider a finite, simple and undirected graph $G=(V,E)$ with $V=\{v_1,\dots, v_n\}$. Let us also fix an integer $k> n/2$. What are we able to say about the following quantity: $$\mathcal{I}_k(G) :=...
0
votes
1answer
53 views

Is graph's planar embedding unique if each block of one planar graph is 3-connected?

A planar graph is one which has a plane embedding. Two drawings are topologically isomorphic if one can be continuously deformed into the other. If we wrap a drawing onto a sphere, and then off again, ...
7
votes
2answers
400 views

Chip-firing clocks

Let $G$ be some outdegree-regular directed graph with $n$ vertices and let $H$ be the Laplacian of $G$, so that the rows of $H$ correspond to chip-firing moves. I’m interested in linear functions $f$ ...
2
votes
1answer
111 views

Directed version of this lemma

On a paper by Shoham Letzter, available Here, there's a lemma that says as follows: Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
1
vote
0answers
123 views

Finding a tree with adjacency matrix near a given matrix

For defining a distance between trees, one can code them into $\mathbb{R}^n$ and use norms in $\mathbb{R}^n$ as distance. (For example we can use adjacency matrices as a tool for this coding) After ...
1
vote
1answer
59 views

“Circuit rank” but for vertices

A graph's circuit rank is the minimum number of edges that have to be removed for the graph to become a tree or forest. Is there a term that represents the minimum number of vertices that we must ...
2
votes
1answer
101 views

Notation for H is isomorphic to a subgraph of G

Is there a notation for the statement $H$ is isomorphic to a subgraph of $G$? I was thinking of using $H<G$, but I'd like to use standard notation if possible.
2
votes
1answer
146 views

Expansion in hypergraphs

Is there a useful concept of expansion in hypergraphs, generalizing the concept for graphs (see: expander graphs)? Of course, expander graphs can be characterized in several qualitatively equivalent ...
0
votes
1answer
49 views

Connected graphs on $\omega$ that “doesn't change” whenever 2 points are collapsed

For any set $X$, let $[X]^2 = \big\{\{x,y\}:x\neq y\in x\big\}$. Let $G=(\omega,E)$ be a connected simple, undirected graph, where $E\subseteq [\omega]^2$.. For $m<n\in \omega$ we let $G/_{\{m,n\}}$...
2
votes
1answer
65 views

Min-sum and min-max node-disjoint path problems

Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now ...
-1
votes
1answer
83 views

Path sequences and isomorphism of graphs

Let $G=(V,E)$ be a finite, simple, undirected graph. For each $v\in V$ we define the path sequence $\text{ps}^G_v: \omega\to \omega$ where $\text{ps}_v(n)$ is the number of vertices that can be ...
3
votes
1answer
68 views

On cospectral graphs

Is there examples of non-isomorphic cospectral graphs having Non-isomorphic automorphism groups? Isomorphic automorphism groups?
5
votes
2answers
271 views

Smallest $3$-regular graph with a unique perfect matching

What is the smallest 3-regular graph to have a unique perfect matching? With a large enough number of nodes, it is possible for a 3-regular graph to have no perfect matching (example can be seen in ...
2
votes
0answers
44 views

Does an $(x, bx)$-biregular graph always contain a $x$-regular bipartite subgraph?

I guess a discrete-mathematics-related question is still welcome in MO since I was new to the community and learned from this amazing past post. The following claim is a simplified and abstract form ...
4
votes
1answer
157 views

Seven Bridges of Königsberg for hypergraphs

I am teaching a course involving hypergraphs. I would like to have a physical analogy/motivating problem for hypergraphs similarly to how the Seven Bridges of Königsberg motivate graphs. Can you help ...

1
2 3 4 5
87