Questions tagged [graph-theory]
Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.
25,010 questions
-1 votes
0 answers
17 views
Graphs where nodes are connected but distant [closed]
Is it possible to make a graph consisting of 2n nodes such that every node is connected to every other node in at least n steps except n of the other nodes? For example with 1, we make the graph with ...
- 45
5 votes
2 answers
117 views
A family of lines with at least four points is 2-colorable
Let $E$ be a finite set of points and $\mathcal{F}$ be a collection of subsets of $E$ (lines) such that each line has cardinal at least 4 two distinct lines intersects at exactly one point. Show ...
- 91
5 votes
0 answers
84 views
The exact meaning of ‘subject to that’ in this context
In the following sentence from the paper (see Page 4, the proof of Lemma 3.4) (see the paper in https://doi.org/10.1016/j.disc.2023.113431) on extremal graphs: Let $G$ be an edge-extremal graph in ...
- 2,815
0 votes
0 answers
20 views
Max–min assignment on a DAG when nodes have candidate values with compatibility constraints
I have a DAG where every node has a (usually small) set of candidate integers. A candidate a is compatible with b if (a | b) or (b | a). For every root I want to choose one candidate per node to ...
- 81
3 votes
2 answers
390 views
Coloring a graph with K-colors
Given a graph, I wish to try and color it with the minimum number of colors (0,1...k). Each 2 connected vertices must have different colors. I proposed the following algorithm - Initialize an array of ...
- 33
-1 votes
1 answer
52 views
Justification for Definition of Directed and Undirected Graph
It is commonly known that directed graphs are defined as a double $G_d:=(V,E)$ such that $E \subseteq V^2$, and that undirected graphs $G_u:=(V,E)$ such that $E \subseteq \left\{ \{a,b\}\Big\vert a \...
- 71
0 votes
0 answers
30 views
The triangulations of one graph all come from the other two [closed]
In graph theory, a triangulation means adding edges to make a graph maximal planar. The following picture is denoted by $G$. The following picture is $G_1$. The following picture is $G_2$. Now ...
- 1,757
2 votes
1 answer
105 views
Are bounds known on the number of quadrilaterals (or 4-cycles) of the putative Conway 99 graph?
The putative Conway $99$ graph is a defined as an undirected graph with $99$ vertices, in which each two adjacent vertices have exactly one common neighbour, and in which each two non-adjacent ...
- 2,441