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
0 votes
0 answers
27 views

Bound for a sequence of vertices in a graph

I have come across the following problem. Let $d\in\mathbb{N}$. Let $G$ be a $k$-regular directed graph with $n$ vertices without parallel edges. For a vertex $v\in G$, let $e_v$ denote the union of $\...
  • 123
5 votes
0 answers
86 views

Goldberg-Seymour conjecture

I am wondering whether the graph theory community regards the Goldberg-Seymour conjecture as settled. According to https://en.wikipedia.org/wiki/Goldberg%E2%80%93Seymour_conjecture, "In 2019, an ...
  • 17.9k
1 vote
0 answers
88 views

Independence number of a grid like graph

Given natural numbers $n$ and $k$, let $G_{n,k}$ denote the simple graph whose vertex set is $\{1,2,\ldots ,n\}$ and there is an edge between $i$ and $j$ when $|i-j|\leq k$. I am interested in the ...
2 votes
1 answer
60 views

Strongly regular graphs with certain parameters

Does there exist a sequence of strongly regular graphs with parameters $(n,d,\lambda,\mu)$ (so every pair of adjacent vertices have $\lambda$ common neighbours, and every pair of non-adjacent ones ...
1 vote
0 answers
38 views

Chromatic number of 2-graph vs hypergraph of point-line incidences

Define the chromatic number $\chi(H)$ of a (hyper)graph $H$ as the smallest $k$ such that its vertices can be $k$-colored such that no (hyper)edge is monochromatic. Given a finite set of points $P$ in ...
  • 17.7k
6 votes
0 answers
79 views

Partial order on graphs induced by homomorphism counts

For graphs $F$ and $G$, let $\hom(F,G)$ denote the number of homomorphisms (adjacency preserving maps) from $F$ to $G$. Define a relation $\le_{\hom}$ on (isomorphism classes of) graphs as $G \le_{\...
9 votes
1 answer
356 views

Is there a program implementation for generating all non-isomorphic graphs with a given degree sequence?

I know the following problem is famous: For a given degree sequence $L$ that is graphic, find an (efficient) algorithm to generate all of the nonisomorphic realizations of $L$. This algorithm is ...
  • 855
3 votes
0 answers
55 views

Research on lower bounds of sphericity of a graph

I am looking for references that address lower bounds on the "sphericity" of a graph. For a finite point set in Euclidean $n$-space, if we connect each pair of points by a line segment ...
5 votes
1 answer
331 views

Six people standing on earth

Consider 6 people $p_i$, $i=1,\dots 6$, standing on a sphere $S^2$. We label the positions of these people by $p_i$ again. Suppose no pair of these points $p_i$ are antipodal. At each point $p_i$ ...
2 votes
0 answers
40 views
+100

What is the analogue of a Block-Cut Tree Decomposition in directed graphs?

Let $G$ be a connected, undirected graph. We define a block $B$ to be a maximal $2$-connected induced subgraph in $G$. It is easy to see that any two distinct blocks are either disjoint or overlap at ...
  • 300
1 vote
1 answer
136 views

Categories associated to digraphs

Let's take a directed graph, or a digraph, $G=(V,E)$ given by a finite set of vertices $V$ and a finite set of edges $E$. We can assume that pairs of vertices can have parallel edges between them and ...
5 votes
0 answers
130 views

What is this Ramsey problem

Given positive integers, $n,m,r$, define $R((n,m);r)$ to be the least $N$ such that for any $r$-coloring $C:E(K_N)\to \{1,\dots,r\}$, there is some monochromatic subgraph with $n$ vertices and $m$ ...
  • 1,921
0 votes
0 answers
79 views

How to find a specific clique cover set?

Let $G(\mathcal{V},\mathcal{E})$ be a graph with vertex set $\mathcal{V}$ and edge set $\mathcal{E}$. Also, non-negative weights $w_i$ are assigned to each vertex $i\in\{1,\ldots,n\}$. Suppose the ...
  • 63
0 votes
0 answers
39 views

Comparing spectral radius of two graphs using the entry of Perron vector

Suppose we have a graph $G$. Let $A$ be the adjacency matrix of $G$ and $x$ be the corresponding Perron vector. Let $x = (x_1,x_2,\cdots,x_n)^t$, where $x_i$ corresponds to the vertex $i \in V(G)$. We ...
  • 199
0 votes
0 answers
38 views

Number of balanced-parentheses sequences on $2n$ bits as $n$ grows large [migrated]

The motivation to consider the sequences below comes from an efficient way to represent trees on $n$ nodes using $2n$ bits. Let $n\in\mathbb{N}$ be a positive integer. Let us call $s\in\{0,1\}^{2n}$ a ...
0 votes
0 answers
165 views

Covering discrete triangle with generalized knight jumps

Consider for $n\in\mathbb{N}, n\geq 6$ the discrete triangle $\nabla=\{(i,j)\in \{1,\ldots,n-1\}^2 \mid j\leq n-i\}$. This is basically the lower "half" of a chess board if you cut it along ...
0 votes
0 answers
61 views

Maximal number of times distance $1$ can occur among $n$ points in the plane [duplicate]

For $n\in\mathbb N$, let $f(n)$ be the maximal number of times distance $1$ can occur among $n$ points in the plane: $$ f(n) = \max_{ \{ x_1,\ldots,x_n \} \subset \mathbb R^2} \# \big \{ i<j : \| ...
8 votes
0 answers
129 views

Explicit constructions of Ramanujan graphs

I am trying to find a list of all the explicit constructions of Ramanujan graphs. By a Ramanujan graph I mean a $k$-regular multi-graph $G$ such that all the non-trivial eigenvalues $\lambda$ of the ...
1 vote
0 answers
37 views

A confusion about the proof of maximal 1-plane graph being $2$-connected

It is well known that every maximal planar graph with at least 4 vertices is 3-connected. But for maximal 1-planar graphs we cannot ensure the high connectivity. (See is-there-any-maximal-1-planar-or-...
  • 855
1 vote
0 answers
50 views

Why is the kernel cyclic if and only if the walk does not backtrack?

I'm reading Mathematics of Isogeny Based Cryptography by Luca De Feo. At some point (pg. 32), he says "A walk of length $e_A$ in the $l_A$-isogeny graph corresponds to a kernel of size $l_A^{e_A};...
0 votes
0 answers
19 views

vertices with least distance to subset of other vertices - Undirected Graph

Given an undirected graph $G=(V,E)$ where $V=\{v_1,v_2,...,v_n\}$ denotes the vertices and $E=\{e_1,e_2,...,e_m\}$ denotes edges. Moreover, there exists a nonnegative weight associated with each edge. ...
  • 1
2 votes
1 answer
131 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} \...
  • 402
3 votes
2 answers
214 views

Hoffman singleton conjecture

So I am currently working on the Hoffman singleton conjecture. For those who do not know this conjecture, it is asking whether there exists a 57-regular, girth 5 graph with $57^2+1$ vertices. While ...
2 votes
0 answers
125 views

Chess pieces metrics in higher dimensions

A couple of days ago, I was thinking about applying the knight (the well-known piece of chess) metric to any cubic lattice $\mathbb{N}^k$, $k \in \mathbb{N}-\{0,1\}$. I suddenly realized that, from $k ...
  • 381
2 votes
2 answers
82 views

The bipartite double of two regular graphs

Is this right? Let G1 and G2 be two regular graphs. If the Kronecker product of the complete graph K2 and G1 is isomorphic to the Kronecker product of the complete graph K2 and G2, then G1 is ...
0 votes
0 answers
52 views

Hadwiger numbers of (-1)-isomorphic graphs

We say that simple, undirected graphs $G, H$ are (-1)-isomorphic if there is a bijection $\varphi:V(G)\to V(H)$ such that for all $v\in V$ we have that the induced subgraphs $G\setminus\{v\}$ and $H\...
0 votes
0 answers
39 views

Complete characterization of graphs with cubicity $\leq 2$

Are there any known complete characterizations of graphs with cubicity $= 2$? (Graphs with cubicity $2$ are those which can be represented as the intersection graphs of squares in $\mathbb{R}^2$) For ...
2 votes
1 answer
112 views

Explicitly known graph families where the product of the size of biggest independent set and biggest clique is "small"

Are there explicit constructions of graph families with the following property: $G_n$ is the graph on $n$ vertices in the family, $\omega(G_n)$ is the size of the biggest clique in the graph $G_n$, $\...
0 votes
0 answers
88 views

An unnamed (perhaps?) graph theory problem

We create a graph weighted $G_0$ given a set of nodes and a function $f(v_x, v_y, G_i) $ that calculates the edge weight between the nodes within $G_0$ that's dependent on the global graph structure. ...
2 votes
0 answers
38 views

Proportion of edges within a fraction of the diameter

Let $G = (V,E)$ be a finite, connected $k$-regular graph of diameter $D$. Fixing some $\epsilon>0$ and letting $v$ be a (random) element of $V$, what proportion of the other edges are at most $\...
6 votes
1 answer
165 views

Lovasz's conjecture for dihedral Cayley graphs

Background: A tantalizing conjecture of Lovasz is the following: Let $G$ be a (finite) connected vertex-transitive graph. Then $G$ contains a Hamiltonian cycle or is one of $5$ counter-examples. (...
  • 1,921
1 vote
0 answers
52 views

Complexity of EFL coloring of a set of lines

Let $M$ be a set of straight lines. Define an EFL coloring of $M$ with $k$ colors as a function $f : P(M) \rightarrow \{ 1,2,\dots,k \}$, such that if two intersection points $p_1, p_2$ belong to the ...
14 votes
1 answer
200 views

Dual polyhedra and electric circuits

Good morning, I hope this question is not too far out of the scope of the forum. I am posting it here because this doesn't seem to be a very standard problem. Yesterday we were calculating the ...
  • 413
3 votes
0 answers
146 views

Behrend's construction vs. Triangle removal lemma

I was reading Zhao's book "Graph theory and additive combinatorics" and on page 71 I came across Remark 2.5.4 which I'd like to understand. Theorem 2.3.1 (Triangle removal lemma) For all $\...
  • 246
5 votes
1 answer
126 views

Graphs without short cycles and with linear number of edges

Let $f : \mathbb{N} \rightarrow \mathbb{N}$ be a non-decreasing function and let $X_f$ be the class of graphs where every $n$-vertex graph $G$ is $(C_3, C_4, \ldots, C_{f(n)})$-free, i.e. $G$ contains ...
  • 645
20 votes
2 answers
737 views

Seymour's second neighborhood conjecture for infinite graphs

Let $G$ be a directed graph (say simple, so no loops and each pair of vertices has at most one directed edge between them). Suppose $G$ is 'locally finite', in the sense that each vertex has only ...
  • 6,333
1 vote
0 answers
65 views

Bipartite graph matching [closed]

Let $G =(X\cup Y, E)$ be a bipartite graph with color classes $X, Y$ and let $M_1$ and $M_2$ be two matchings in $G$. We have to prove that there exists a matching $M\subseteq M_1\cup M_2$ which ...
0 votes
2 answers
62 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=...
  • 143
8 votes
0 answers
233 views

Did these graphs pop up somewhere?

Please let me know if the following graphs popped up in some problems. Each of these graphs is described by 5 integers $n_1\geqslant k_1$, $n_2\geqslant k_2$, $l\geqslant 0$. We take two complete ...
3 votes
1 answer
119 views

Representing graphs by $\text{Hom}$-graphs

Let $G, H$ be simple, undirected graphs. A graph homomorphism from $G$ to $H$ is a map $f:V(G)\to V(H)$ such that whenever $\{v,w\}\in E(G)$ then $\{f(v), f(w)\}\in E(H)$. Let $\text{Hom}(G,H)$ be the ...
5 votes
1 answer
100 views

Completing subcubic trees to cubic graphs

A graph theory question: For given girth g, does there exist $n_0(g)$ such that any tree $T$ of even order $n \geq n_0(g)$ and maximum degree $\Delta(T) \leq 3$ can be completed to a cubic graph with ...
0 votes
0 answers
130 views

Impact of the global cost function (weighting) to Betweenness Centrality distribution

I have a graph whose edges have all a weight of 1. In my particular case computing the Betweenness centrality by counting shortest paths between all pairs results ...
4 votes
0 answers
146 views

Name for a chain-like graph

Is there a name for graphs of the following type? Namely, it has an integer function $\ell$ on the set of the vertex set such that $v$ is adjacent to $w$ if and only if $$|\ell(v)-\ell(w)|\le 1.$$ ...
4 votes
1 answer
435 views

Turán's theorem for cosets of groups

Let $G$ be a finite group, $G',H$ be its subgroups and $H'=G'\cap H$. For each $g\in G$, we create a map $f_g:G'/H'\rightarrow G/H: aH'\rightarrow gaH$. It's easy to see that the map is well defined ...
1 vote
1 answer
81 views

Finding $k$ active elements by evaluating the "any-operator" of subsets of variables

Assume a set $S$ of elements $\{s_1,\dots,s_n\}$, each which has a hidden label 'active' or 'inactive'. Assume there are $m\ll n$ active elements in total. You are allowed to iteratively perform a ...
9 votes
0 answers
136 views

Number of triangle-free graphs with prescribed number of edges

This question is posted from StackExchange since it received no answer there. Let $f(n, e)$ be the number of triangle-free graphs on $n$ vertices and $e$ edges. From empirical evidence, I am motivated ...
  • 211
1 vote
0 answers
58 views

Graph removal lemma

The graph removal lemma says that for any graph $H$ and any $\epsilon>0$, there is a $\delta>0$ such that any $n$-vertex graph which contains at most $\delta n^{v(H)}$ copies of $H$ can be made $...
  • 171
1 vote
0 answers
85 views

When do two path algebras share an underlying graph?

Suppose $Q$ and $Q'$ are two quivers. I am curious as to what relation $\mathbb{C}Q$ bears to $\mathbb{C}Q'$ when $Q$ and $Q'$ share the same underlying graph and only differ by direction. Since ...
  • 385
2 votes
0 answers
42 views

A variant of the regularity lemma that depends on the number of vertices

Suppose $G = (U \cup V,E)$ is a bipartite graph with $n$ vertices on each side. For sets $X \subseteq U$ and $Y \subseteq V$, let $d(X,Y) = |(X \times Y) \cap E| / (|X||Y|)$ denote the edge density ...
  • 357
2 votes
1 answer
86 views

"Combined" chromatic number of $2$ graphs glued together with $2$ edges per vertex

If $X$ is any set, we let $[X]^2:=\big\{\{x,y\}:x\neq y\in X\big\}$. If $G=(V,E)$ is an undirected graph and $v\in V$, we define $N_G(v) = \{w\in V:\{v,w\}\in E\}$. For $i =1,2$, let $G_i=(V_i,E_i)$ ...

1
2 3 4 5
97