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
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 ...
Sergi's user avatar
  • 79
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 ...
ahsalden's user avatar
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$-...
Zach Hunter's user avatar
  • 3,393
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 ...
Dominic van der Zypen's user avatar
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 ...
F J's user avatar
  • 161
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 ...
Samuel Elman's user avatar
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 ...
Ron P's user avatar
  • 947
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 ...
Manfred Weis's user avatar
  • 12.6k
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 ...
Dominic van der Zypen's user avatar
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 ...
Sam van G's user avatar
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 ...
Kregnach's user avatar
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 ...
L.C. Zhang's user avatar
  • 1,605
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}\...
domotorp's user avatar
  • 18.3k
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 ...
M. Winter's user avatar
  • 12.5k
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 ...
user2512443's user avatar
-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? ...
Math_deep's user avatar
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 ...
Isomorphism's user avatar
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]. ...
L.C. Zhang's user avatar
  • 1,605
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 ...
thematdev's user avatar
  • 163
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 \...
Dominic van der Zypen's user avatar
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 ...
Usama Waheed's user avatar
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-...
tmh's user avatar
  • 685
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 ...
Stefan Steinerberger's user avatar
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 ...
Jose Antonio Martin H's user avatar
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, ...
Taras Banakh's user avatar
  • 40.8k
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 ...
Salma Omer's user avatar
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 ...
JoshuaZ's user avatar
  • 6,090
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:...
J.Doe's user avatar
  • 101
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 ...
Tomi's user avatar
  • 101
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$. ...
fawadria's user avatar
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 ...
nabil's user avatar
  • 51
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 ...
user508346's user avatar
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 ...
Wolfgang's user avatar
  • 13.2k
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. <...
L.C. Zhang's user avatar
  • 1,605
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 ...
L.C. Zhang's user avatar
  • 1,605
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$...
Brendan McKay's user avatar
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 ...
Zach Hunter's user avatar
  • 3,393
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?
Leo Marcus's user avatar
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$ ...
MathManiac's user avatar
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 ...
kreitz's user avatar
  • 53
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....
Jens Fischer's user avatar
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 ...
CWC's user avatar
  • 359
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 ...
Pritam Majumder's user avatar
-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 ...
joro's user avatar
  • 24.2k
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,...
Rouhollah Mofid's user avatar
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). ...
tim guo's user avatar
  • 11
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 ...
vidyarthi's user avatar
  • 2,007
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 ...
Lance's user avatar
  • 203
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 ...
mahu's user avatar
  • 63

1
3 4
5
6 7
103