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
7
votes
1
answer
483
views
Is End() a functor from the category of directed graphs to the category of monoids?
As the title says, I've been interested for a while in seeing if the assignment End(G) for directed graphs G can be made functorial, for some not-so-obvious choice of mapping for the corresponding ...
0
votes
0
answers
90
views
Reformulate Traveling Salesman Problem in areas traversed problem
I was wondering whether one has ever considered to reformulate TSP in terms of the areas traversed in either direction. Thus take three initial points of the solution they span a triangle with a ...
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$-...
0
votes
1
answer
48
views
Minimal dominating sets in flat graphs
Suppose that $G=(V,E)$ is a simple, undirected graph. We say that $D\subseteq V$ is dominating if for all $v\in V\setminus D$ there is $d\in D$ such that $\{v,d\}\in E$. We say $D$ is minimal ...
3
votes
1
answer
106
views
Spectrum of the adjacency matrix of certain directed graphs
For an undirected graph $G$, its adjacency matrix $A_G$ is symmetric, and by the (consequence of) spectral theorem, each of its Jordan blocks has size $1$. This is not true for a general directed ...
5
votes
2
answers
186
views
Connectivity graph invariant
I am interested in the following graph invariant: for a given graph $G=(V,E)$, $c(G)$ is defined to be the smallest number of vertices such that I can recreate the connectivity of $G$ by disconnecting ...
0
votes
0
answers
40
views
Properties of preferential attachment such as spectral gap
Short question:
Is there a good math reference on the properties of preferential attachment graphs? In particular, expansion properties seem to interest me.
More details:
I try to investigate the ...
0
votes
0
answers
4
views
Statistics of connected-component sizes of minimum-weight $f$-factors in random planar geometric graphs
An $f$-factor is an $f$-regular subgraph with the same vertex set $V$ and a subset of the edges $E$ of some given undirected graph $G(V,E)$
Question:
what is known about the statistical properties of ...
3
votes
1
answer
121
views
The sequence of the power chromatic numbers $(\chi(G^n))_{n\in\mathbb{N}}$
For any finite, simple, undirected graphs $G, H$ we denote by $G\times H$ their categorical product. For any graph $G$ we let $G^1 = G$ and for $n\geq 1$ we let $G^{n+1} = G \times G^n$.
It is easy to ...
9
votes
3
answers
524
views
Deciding homomorphic images of De Bruijn graphs
The De Bruijn graph $B_n$ of
dimension $n$ (on the two-letter alphabet) is defined as the directed graph on
$2^n$ vertices and $2^{n+1}$ edges, where for every $w = w_0 \dots w_n \in
2^{n+1}$ we put ...
0
votes
3
answers
124
views
Even regular planar graphs without 2-cycles
Related to another question I asked, some questions came up, the most important is the following:
Are there any 4-regular planar graphs without 2-cycles + 3-cycles?
Could someone draw an example if ...
0
votes
0
answers
56
views
Are almost all subsets with cardinality at least the connectivity also separating sets?
Let $G:=(V,E)$ be a graph. If $S \subseteq V(G)$ and $G-S$ is not connected, then $S$ is a separating set. The vertex connectivity, denoted by $\kappa(G)$ of a graph $G$ is the cardinality of a ...
2
votes
1
answer
126
views
Turán density of hypergraphs with very few edges
As usual, for an $r$-uniform hypergraph $G$, denote by $ex_r(n,G)$ the maximum number of edges an $r$-uniform, $G$-free hypergraph on $n$ vertices can have, and let $\lim \frac{ex_r(n,G)}{\binom nr}\...
2
votes
1
answer
159
views
Are there many self-complementary perfect graphs?
A graph is perfect if it has no induced subgraph that is either an odd cycle (other than a triangle) or a complement thereof (note that the class of perfect graphs is closed under graph complement). A ...
1
vote
1
answer
63
views
$A^*$ algorithm to find shortest path when weights in my graph are the inverse of distance
Given a graph G=(V,E) where the weights on my edges are inverse of Euclidian distance between nodes, I want to know if I can use A* algorithm to find the shortest path. How I need to modify the ...
-1
votes
1
answer
115
views
A permutation and combination problem about the number of connections in a sequence of n numbers [closed]
There is a sequence of n numbers as 1,2,3,...,n
How many combinations of the connections between two numbers in the sequence without overlaping?
...
0
votes
0
answers
69
views
Perfect graphs are normal graph
Let $G$ be a graph. We call $G$ normal if it admits two partitions: $V(G)=\bigcup \mathcal{I}=\bigcup \mathcal{C}$ where $\mathcal{I}$ is a collection of independent sets and $\mathcal{C}$ is a ...
0
votes
0
answers
56
views
Non-planar non-Hamiltonian chordal graphs with toughness greater than 1
The following article tells us that every planar chordal graph with toughness greater than 1 is Hamiltonian.
Böhme T, Harant J, Tkáč M. More than one tough chordal planar graphs are Hamiltonian[J]. ...
6
votes
1
answer
241
views
Pair matching between divisors less and more than $\sqrt{N}$
Let $n$ be the positive integer. Let $A$ and $B$ be sets of divisors of $n$ less and more than $\sqrt{n}$ respectively.
Consider bipartite graph $(A, B)$, where two vertices are connected when one ...
2
votes
2
answers
61
views
Does $(\omega, E)$ with the cycle condition have an $\omega$-path?
Let $G = (V,E)$ be a simple, undirected graph. We say that $v\neq w\in V$ lie on a common cycle if there is an integer $n\geq 3$ and an injective graph homomorphism $f: C_n\to V$ such that $v,w\in \...
1
vote
0
answers
42
views
Python code for finding the total number of connected graphs that has a Cospectral and Coinvariant mates for several graph assosiated matrices [closed]
I am looking for a python code for finding the total number of connected graphs of order upto 10 that has a cospectral and coinvariant mates for several graph assosiated matrices. Two graphs are ...
6
votes
0
answers
132
views
Graph-theoretic quasi-crystals?
I have recently been interested in the following purely graph-theoretic notion that weakens the assumption of transitivity in a similar way to how quasi-crystals have "(possibly) aperiodic long-...
7
votes
1
answer
306
views
Diameter bound for graphs: spectral and random walk versions
This question can be phrased in different settings. I will discuss a spectral formulation and the equivalent random walk version. The question came up naturally in recent work with Devriendt and ...
5
votes
1
answer
104
views
Sufficient condition for a Hamilton cycle $C$ in a planar triangulation $G$ s.t. every triangle in $G$ has an edge in $C$
Let $G$ be a $k$-connected planar triangulation ($k\geq 4$) and let $C$ be a Hamilton cycle of $G$. Then:
Which conditions would be sufficient to assure that every triangle of $G$ has at least one ...
6
votes
1
answer
341
views
Desargues ten point configuration $D_{10}$ in LaTeX
I want to draw the Desargues configuration $10_3$ in LaTeX using the standard picture environment, which allows only lines with the slopes $n:m$ where $\max\{|n|,|m|\}\le 6$. Is it possible? If not, ...
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 ...
1
vote
0
answers
46
views
Edge contractions of a graph but only along maximum cliques
Consider the following operation to an undirected graph: one is allowed to take any maximum clique and replace the clique with a single vertex which is attached to every single vertex which has an ...
0
votes
0
answers
39
views
Is it always possible to create a minimum depth tree where tree nodes are unique and have a 'choice'?
This is a somewhat long question thus sincere apologies beforehand. In a tree a node is a simple point. Now instead of a node let us consider a set of 'choice nodes' that have the following properties:...
0
votes
0
answers
64
views
Adapting Held–Karp algorithm to visit groups of vertices
The Held–Karp algorithm has exponential time complexity $\Theta\left(2^n n^2\right)$, which is better than brute forcing the TSP which requires $\Theta(n !)$.
I'm interesting in amending the Held–Karp ...
1
vote
0
answers
73
views
Constructing orientations that increase (directed) distances between vertices in a maximum independent set
An orientation of a simple undirected graph $G=(V,E)$ is a directed graph $G' = (V,E')$ that is constructed by including either $(u,v) \in E'$ or $(v,u) \in E'$, but not both, for all $(u,v) \in E$.
...
5
votes
0
answers
115
views
The Smith decomposition of the graph Laplacian and Locality
Let $X$ be a graph. Let $V(X)$ and $E(X)$ be the sets of vertices and edges of the graph respectively. If $f:V(X) \rightarrow G$ where $G$ is an abelian group, then one can define a graph Laplacian as ...
0
votes
0
answers
56
views
Complexity of vertex separator problem
Given a graph $\Gamma=(V,E)$ with vertex set $V$ and edge set $E$, a three-partition is a decomposition of $V$ into a triple $(V_1, S, V_2)$ such that vertices of $V_1$ are only incident to vertices ...
4
votes
1
answer
104
views
Are there decompositions of $K_{16}$ by certain 3-regular graphs?
This is inspired by the problem of the Hoffman-Singleton Decomposition of $K_{50}$. I wanted to look at smaller variants of this kind of problem, and so naturally I started wondering:
Can the (edges ...
4
votes
0
answers
201
views
How many 20-vertex 2-connected 5-regular non-Hamiltonian graphs are there?
As for the question in title, I attempted to use nauty to obtain them, but it has been running on my computer for nearly three days without producing any results.
<...
2
votes
1
answer
186
views
How can one construct a class of $k$-connected $k$-regular bipartite graphs with the girth of (at most) $k-1$?
I would like to construct a class of $k$-connected $k$-regular bipartite graphs with the girth at most $k-1$.
This problem arises from a cycle.
Any 2-connected 2-regular graph is a cycle, but its ...
8
votes
0
answers
155
views
Hamiltonian paths in the prime sum graph
The following is a generalization of this old question .
Let $n\ge 2$, $[n]=\{1,\ldots,n\}$. For which distinct $a,b\in[n]$ is it possible to list $[n]$ in some order $x_1,\ldots,x_n$ such that $x_1=a$...
1
vote
0
answers
59
views
Correct dependence for "Local Coloring"
In Alon-Spencer's book, Probabilistic Lens #8, it is proven that for each $k$, there exists $\epsilon = \epsilon(k)>0$ such that for all large $n$, there exists an $n$-vertex graph $G$ with ...
20
votes
2
answers
1k
views
Non-definability of graph 3-colorability in first-order logic
What is a proof that graph 3-colorability is not definable in first order logic? Where did it first appear?
1
vote
0
answers
137
views
Generalizing Hall's marriage theorem
(This question was earlier posted on stackexchange: Generalizing Hall's marriage theorem. As it received no answers there, I am reposting it here for more attention.)
Fix positive integers $m,n,k$ ...
22
votes
4
answers
3k
views
Brute force open problems in graph theory
Usually, a graph theoretic problem asks whether some class of graphs $C$ possesses a quality $P$. For example, $C$ is the class of all graphs and $P$ is the reconstructability property in Kelly-Ulam ...
2
votes
1
answer
103
views
If you have three paths from vertex x to vertex y, when are you guaranteed a cycle which contains both x and y?
Let G be an undirected, simple graph containing distinct vertices x and y. Let P,Q,R be three distinct paths in G from x to y. We can assume the graph G is only those paths (any vertex in G is in one ...
2
votes
1
answer
78
views
"Balanced" separator which is independent set
I am looking for existence results on separators of $r$-regular graphs $G=(V,E)$, which have the property that
$S\subset V$ is a separator
for all $v,w\in S$ the edge $\langle v,w\rangle\not\in E$ (i....
1
vote
0
answers
79
views
Fractal dimension of a self-similar tree
Consider a binary tree constructed as the following. Given a node with a some value $x$, I construct two children nodes each having value $l(x)$ and $r(x)$ respectively. I repeat the same on the ...
2
votes
0
answers
98
views
Regarding rigid graphs in the plane
Quoting from the book (page 272) Graphs and Geometry by Lovasz, we have the following theorems regarding the characterization of rigid graphs in the pane.
Theorem 1: A graph $G$ is rigid in the plane ...
-2
votes
2
answers
212
views
Must an isomorphism preserving graph transformation preserve the order of the automorphism group?
Let $F$ be some function graph to graph which preserve graph isomorphism.
Example of such $F$ are the line graph, the $k$-subdivision of $G$
and many others.
$F$ need not preserve the order, the ...
1
vote
1
answer
126
views
Complete minor graphs
Is there any result or known way to find complete minors of graphs? I want to find complete minors of generalized Petersen graphs and $3$-regular graphs. I guess that generalized Petersen graphs $G (n,...
1
vote
1
answer
263
views
Counting $n$-edge directed graphs
I would like to count the $n$-edge directed graphs. The graphs might contain self-loops (edges connecting a vertex to itself) and multiple edges (multiple edges connecting the same pair of vertices). ...
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 ...
0
votes
0
answers
23
views
Canonical information geometry for probability distributions on different parameter spaces
I am interested in a canonical information geometry on spaces of probability distributions containing distributions with different parameter spaces. Let me give some context and practical motivation ...
3
votes
0
answers
123
views
A class of Kripke frames which preserves validity
The background of our discussion is intuitionistic logic, i.e. the following definitions are intuitionistic Kripke frame.
For $1\leq s\leq n-2$, the frame $\mathcal{C}_n(s)$ denotes the frame which is ...