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.
5,150
questions
2
votes
1
answer
224
views
Union closed family of sets with at most a certain number of couples of sets with non-empty intersection
Is it possible to find a union closed family $\mathcal{F}$, $\emptyset \notin \mathcal{F}$, with $|\mathcal{F}| = n$ sets, such that there are at most:
$$\left(1-\frac{1}{\left\lfloor \frac{n-1}{2} \...
1
vote
1
answer
262
views
maximal sets of vertices that avoids a clique
I am looking for some known algorithm that finds, for a given graph, all the maximal sets of vertices that avoid a clique of some given size $k$. I'd prefer one written in MATLAB, but other languages ...
1
vote
0
answers
157
views
Locally "unshortable" paths in graphs
Setup: Consider a connected graph G, with diameter "d".
Informally: Trivially (by definition of diameter), taking any path $P$ any nodes $P(i) , P(i+k)$ for $k>d$ can be connected by a ...
3
votes
1
answer
133
views
Conditions on graphs to assure unique embedding on a fixed genus surface
The classical Whitney Theorem in low topological theory/graph theory states that every 3-connected planar graph is uniquely embeddable (up to orientation) on the sphere.
My question is the following: ...
4
votes
1
answer
136
views
Sizes of triangle-free graphs with independence number $k$
A triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. The independence number $α = α(G)$ of a graph $G$ is the cardinality of a maximum in dependent set of ...
22
votes
2
answers
879
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 ...
3
votes
0
answers
62
views
Second eigenvalue of primitive matrix
Let $A$ be a primitive $N\times N$-matrix with positive entries, that is there is $n>0$ such that $(A^n)_{i,j}>0$ for all $i,j$. For brevity, assume the entries consist only of $0$ and $1$.
The ...
4
votes
0
answers
126
views
"Neighborhood-Bounded" regular graphs
Lately I have been interested in questions surrounding strongly regular graphs, and came across this question that I have been struggling to make progress on. (For the sake of being explicit, a graph $...
0
votes
0
answers
86
views
Hypergraphs where the edges are subsets of the union of the edges and nodes?
Is there a formulation of hypergraphs such that the hypergraph $H = (V, E)$ consists of a set of nodes $V = \{v_1, v_2, ..., v_n\}$ and a set of edges $E = \{E_1, E_2, ...,E_m\}$, where $E_i \subseteq ...
10
votes
1
answer
549
views
Are there two-sided $\varepsilon$-expanders with independent sets of size $(1-\varepsilon)n$?
Terry Tao's notes on expander graphs has the following exercise:
Exercise 13 Let $G$ be a $k$-regular graph on $n$ vertices that is a two-sided $\epsilon$-expander for some $n > k \geq 1$ and $\...
2
votes
1
answer
80
views
A reference for Wagner's Theorem
In the course of a project I am developing I have to use a classical result in topological graph theory due to Wagner in which Wagner gives the precise structure of graphs in which $K_5$ is excluded ...
23
votes
1
answer
1k
views
Universal graph
A connected (and infinite) graph $U$ will be called $n$-universal if any connected graph with degree $\leqslant n$ admits an embedding in $U$.
Is there a 3-universal graph with bounded degree?
3
votes
1
answer
90
views
Hamiltonian paths in 2-generated (Cayley) circulant digraphs. A counterexample?
Circulant digraphs are Cayley digraphs of cyclic groups. My question refers to hamiltonian paths (not to hamiltonian cycles) in 2-generated circulant digraphs (not graphs).
There is a theorem by ...
1
vote
0
answers
140
views
Optimal covering trails for every $k$-dimensional cubic lattice $\mathbb{N}^k := \{(x_1, x_2, \dots, x_n) : x_i \in \mathbb{N} \wedge n \geq 3\}$
After a dozen years spent investigating this particular class of problems, I finally give up and I wish to ask you if any improvement is achievable from here on.
The general problem is as follows:
Let ...
6
votes
1
answer
331
views
Finding minimum operations to move ants through connected graph
I am working on a project that requires to find the minimum number of steps to move ants from source to sink in a graph; one step is the movement of all ants from one node to the next of the graph. ...
13
votes
1
answer
375
views
Two-player independent set game
Let $G = (V, E)$ be a finite graph, and $S \subseteq V$ initially be an empty set. Alice and Bob play a game, making moves in turns starting with Alice. A move consists of choosing a vertex $v \in V \...
0
votes
2
answers
191
views
Compute the average path weights of paths with the same path length in a directed acyclic graph (DAG)
Given a weighted directed acyclic graph (DAG) $G=(V,E)$ with each edge $e\in E$ has a non-negative weight $w(e)$. For a path $p=(e_1,e_2,\dotsc,e_n)$ in $G$, define the path weight as : $w(p)=\sum_{i=...
2
votes
1
answer
311
views
Worst case performance of heuristic for the non-Eulerian windy postman problem
The windy postman problem seeks the cheapest tour in a complete undirected graph, that traverses each edge at least once; the cost of traversing an edge is positive and may depend on the direction, in ...
6
votes
3
answers
779
views
Connected graphs isomorphic to their own contraction
Let $G = (V, E)$ be a simple, undirected graph with $|V|>2$, and let $S\subseteq V$ be a set with more than $1$ element. By $G/S$ we denote the graph obtained by collapsing $S$ to one point. More ...
1
vote
1
answer
78
views
Generating 12-vertex plane graphs with 2 faces of degree 3 and all other faces of degree 4
My question may be similar to generating-21-vertex-4-regular-plane-graphs-with-8-faces-of-degree-3-and-15-face., but it has differences. The plane graphs I desire (without needing regularity) have ...
8
votes
1
answer
719
views
6-regular bipartite graphs with no 8-cycles
I'm looking for simple 6-regular bipartite graphs with no 8-cycles, as small as possible. It doesn't matter if there are 4-cycles or 6-cycles, provided there are no 8-cycles. Such graphs must exist ...
8
votes
2
answers
2k
views
How to prove a random d-regular graph is an expander with prob >= 0.5?
How to prove a random $d$-regular graph is an expander with prob $\ge 0.5$?
Context: Many resources, like
http://math.mit.edu/~fox/MAT307-lecture22.pdf
state the theorem in the general case, but then ...
2
votes
1
answer
135
views
First known proof of the $2 \cdot n-2$ Theorem for the planar generalization of the Nine dots problem
Reading the Wikipedia page about the well-know Nine dots puzzle, I have just seen that the planar generalization of this problem would have been proven in 1956 (see Wikipedia: Nine dots puzzle), while ...
4
votes
0
answers
808
views
Number of arrangements that contain at least 1 path from top to bottom of 2D matrix
I have a $n\times n$ matrix of objects. $n'$ objects are black, and the rest $n^2-n'$ are white.
With that information, I can easily calculate the total number of black element arrangements that exist ...
0
votes
2
answers
109
views
Why is a plane graph Delaunay realizable if stellating a face makes the graph inscribable?
I have come across the following lemma in several papers (for instance see lemma 2.2 in this) (and some authors state this the proof immediately follows from basic properties of the stereographic ...
4
votes
0
answers
116
views
Reorganizational matching
Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
5
votes
1
answer
346
views
Details of generation programs supplied with nauty
The program nauty comes with gtools which contains, among others, several generation programs like geng, genbg, ... I was ...
0
votes
1
answer
65
views
Number of bi-directional (or symmetric edges) [closed]
I am trying to figure out the least number of directed edges that would be bi-directional after constructing a graph with $2k-1$ nodes that are each $k$ in-degree. For example, $2(2)-1=3$ nodes that ...
1
vote
0
answers
54
views
Possible variant of Lovász: Graphs without 3 vertex-disjoint cycles
Is there a classification, or perhaps some exhaustive description, of graphs without 3 vertex-disjoint cycles,
and/or do you maybe know about some reference for such?
The case of graphs without 2 ...
1
vote
1
answer
131
views
Connected sets with a large boundary in a privileged set
Let $G=(V,E)$ be a connected, undirected graph. Define the boundary $\partial S$ of a set $S\subset V$ to be the set of all $v\notin S$ joined to $S$ by an edge, i.e.
$$\partial S = \{v\not \in S: \...
6
votes
1
answer
337
views
Probabilistic problem on random spanning trees
Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$....
3
votes
1
answer
161
views
Subset of the vertices in a tournament
Suppose we have a directed complete graph. Can we always find a subset $S\neq \emptyset$ of the vertices such that for every vertex $v$, $v$ has incoming edge from at least $\dfrac{|S|}{2}$ of the ...
7
votes
2
answers
561
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
0
answers
59
views
Can the sequence of complete graphs coarsely embed into Hilbert space?
Basically the title. If I have the metric space which is the disjoint union of the sequence of complete graphs, and the usual graph metric, has it been shown that the metric space can be coarsely ...
2
votes
0
answers
83
views
Computationally decomposing a complete geometric graph into forests of stars
I'm working on the following problem:
I would like to see if it possible to decompose a complete geometric graph on $8$ vertices into $5$ planar star-forests. As doing this by hand was hopeless, I ...
2
votes
2
answers
225
views
Finding an easy example applying the general Lovász local lemma
Is there any easy application for the general local lemma as follows? If someone knows, please tell me the references or just post an example here. Thanks.
General Lovász local lemma: Consider a set $...
2
votes
2
answers
91
views
Real-world datasets for testing the maximum edge bi-clique problem
We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...
0
votes
0
answers
48
views
Clique sizes of generalized Kneser graphs
Are there known bounds for clique size in generalized Kneser graphs $KG(n,k,t)=K(n,k,t-1)$, the graph formed by distinct $k$ subsets of $n$ set so that two subsets with at most $t$ elements in common ...
0
votes
0
answers
55
views
Cycles in Kneser graphs with three vertices forming triangles
Consider the Kneser graphs $G=K(n,k)$. Is it possible to list how many even cycles, or, at the least, existence of an even cycle of a given order in $G$, such that any three consecutive vertices form ...
2
votes
1
answer
322
views
What's the worst case for strongly regular graph's isomorphism algorithm?
A new algorithm of Graph Isomorphism is invented by PCT/CN2020/134861, roughly speaking time complexity $\leqslant5n^2$ except for regular graph, automorphism group can be known as by-product. Peer ...
9
votes
2
answers
636
views
Does every big polyomino contain a big arithmetic progression?
Define a $k$-AP (arithmetic progression) as $k$ vertices whose $x$- and $y$-coordinates both from an arithmetic progression, for example, (1,0), (2,2), (3,4) is a 3-AP.
Is it true that for every $k$ ...
5
votes
3
answers
2k
views
Effect of different graph operations on spectrum of graph laplacian?
The algebraic connectivity of a graph G is the second-smallest eigenvalue of the Laplacian matrix of G. This eigenvalue is greater than 0 if and only if G is a connected graph. The magnitude of this ...
2
votes
0
answers
41
views
Regularize a graph while embedding the spectrum of adjacency matrix
Given an irregular graph $G$ whose maximum degree is $d$, I am interested in producing a new graph $G'$ which is regular and has the spectrum of the adjacency spectrum of $G$ embedded in the spectrum ...
1
vote
2
answers
125
views
Constants for diagonal hypergraph Ramsey Theorem
For integers $n,s$, we write $K_n^{(s)}$ to denote the complete $s$-uniform hypergraph on $n$ vertices.
Given integers $k,s,r$, let $R(K_k^{(s)};r)$ denote the smallest $N$ such that, for every $r$-...
10
votes
2
answers
2k
views
When are the adjacency matrices of non-isomorphic graphs similar?
From Wikipedia.
In linear algebra, two n-by-n matrices A and B are called similar if
$$ B = P^{-1} A P$$
for some invertible n-by-n matrix $P$.
If $P$ is a permutation matrix, $A$ and $B$ are ...
1
vote
1
answer
233
views
Choosing sets with a few properties from a given set of elements
Fix $n$ and $k$ with $n \geq 2k+1$. Let $X$ be an $n$ element set. Let $\binom{X}{k}$ denote the collection of $k$-element subsets of $X$. Suppose that $\mathcal{Y} \subseteq \binom{X}{k}$ is a family ...
0
votes
0
answers
39
views
Determining homomorphism using automorphism group of two graphs
I wish to know the connection between the automorphism group of two graphs and homomorphism between them, if any.
Like all Kneser graphs $K(n,k)$ have the same automorphism group $S_n$. But, given ...
0
votes
0
answers
37
views
Fiedler vector of an abstract simplicial complex and partitioning
Let $G=(V,E)$ be a connected graph, and $L = A - D$ the corresponding graph Laplacian. The second smallest eigenvalue of $L$, $\lambda_1$, is Fiedler's value, and the associated eigenvector, $\phi_1$, ...
1
vote
2
answers
125
views
Regarding a specific Turán number of graphs
I wish to know the latest bound on the number of edges a graph of girth greater than or equal to $t$ can have.
Specifically, I heard somewhere that a graph of girth greater than or equal to $t$ can ...
6
votes
0
answers
122
views
Do vertex-maximal paths in 4-connected graphs intersect?
Call a path in a (possibly infinite) graph vmax (for vertex-maximal) if there is no path that covers a containmentwise larger subset of vertices.
For example, in any spider graph the union of any two ...