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