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

learn more… | top users | synonyms

0
votes
0answers
20 views

Looking for an example of a contour integral with matrix entries

Let $A$ be a matrix (if needed assume it to be the adjacency matrix of graph). Let one be given two functions $P(z)$ and $Q(z,A)$ such that both are polynomials in $z$ and $A$, where $z$ is some ...
4
votes
2answers
106 views

How many simple cycles can a graph with $n$ vertices and $m$ edges have?

I am mainly interested in the smallest number of simple cycles a graph with $n$ vertices and $m$ edges must have. For example, if $m\le n-1$, this number is $0$, then if $n\le m \le 3(n-1)/2$, it is ...
-1
votes
0answers
64 views

Are Modular Collatz Graphs strongly connected? [on hold]

A while ago, I stumbled on the idea of representing the Collatz function, modulo a prime $p$, as a directed graph. Define, as usual $$ T(x) = \begin{cases} (3x+1)/2 & \text{if $x$ is odd,} \\ x/2 ...
-2
votes
0answers
33 views

Find a shortest way between nodes in graph [on hold]

I have a next structure : Each node in graph may have more than 2 links. I want to find a shortest way with node 1 and 13. ...
7
votes
1answer
93 views

Is there a Degenerate Dependency Local Lemma?

The Lovasz Local Lemma has several generalizations, with names usually starting with L, such as Lopsided or Lefthanded. Here I ask whether another possible generalization (for which I could not yet ...
18
votes
0answers
251 views

3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$. Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = ...
3
votes
2answers
126 views

The Hadwiger number of $L(K_n)$

For $n\in\mathbb{N}$ we consider the set $\{1,\ldots,n\}$ and define the line graph $L(K_n)$ of the complete graph $K_n$ as follows: $V(L(K_n)) = \big\{\{a,b\}: a,b\in \{1,\ldots, n\}, a\neq b ...
1
vote
1answer
108 views

Implication between Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture?

The Erdös-Faber-Lovasz conjecture and Hadwiger's conjecture can be stated in a very similar form: Erdös-Faber-Lovasz conjecture: for all finite simple undirected graphs $G=(V,E)$ we have $\chi(G)\leq ...
9
votes
3answers
644 views

Is every graph an edge-crossing graph?

Consider a circular drawing of a simple (in particular, loopless) graph $G$ in which edges are drawn as straight lines inside the circle. The crossing graph for such a drawing is the simple graph ...
4
votes
4answers
255 views

Request for examples of 4-regular, non-planar, girth at least 5 graphs

Edit: As David Eppstein points out (in his answer below) the assumption that the graph is non-planar is redundant. Thank you to everyone who answered/commented. I have a problem about geometric ...
2
votes
1answer
36 views

Adding vertex-disjoint edges to reduce the diameter

Let $G=(V,E)$ be a finited connected graph, $V\neq \emptyset$. Let $[V]^2 := \big\{ \{v,w\}: v, w \in V\text{ and } v\neq w\big\}$. Given $F\subseteq [V]^2$ we say that $F$ is a vertex-disjoint ...
1
vote
0answers
9 views

Is it true that centrality measures in SNA are indicative for most important vertices only?

I read about the limitations of centrality measures on Wikipedia. It says that centrality measures are good only for identifying top most important nodes in a social network. Their relative values can ...
1
vote
1answer
112 views

Is the number of vertices bounded for fixed max degree and fixed diameter?

Are there positive integers $\Delta, d$ such that the following statement is true? For every $n\in \mathbb{N}$ there is a graph $G = (V,E)$ such that $|V| = n$, $\Delta(G) \leq \Delta$ ...
3
votes
1answer
89 views

Diameter of sum-graph over a meager set

We say that $S\subseteq \mathbb{N}$ is meager if $$\text{lim sup}\frac{S\cap\{1,\ldots, n\}}{n} = 0.$$ Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where ...
1
vote
1answer
32 views

Connected components of a sum-graph over an infinite set

Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$ Is there an infinite subset ...
0
votes
1answer
57 views

Edge-disjoint cycles in graphs

Given a graph $G=(V,E)$ and a fixed integer $k$ are there any algorithms known which would find the maximum number of edge-disjoint cycles of length $k$ in $G$? If not is there a proof that this ...
6
votes
1answer
109 views

Diameter of sum-graph over a non-meager set

Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$ We say that $S\subseteq ...
0
votes
1answer
37 views

Sum-graph over an infinite set

Given $S\subseteq \mathbb{N}$, we associate to $S$ the sum-graph $G_S = (\mathbb{N}, E)$ where $$E = \big\{\{m,n\}: m,n \in \mathbb{N} \text{ and } m+n\in S\big\}.$$ If $S$ is infinite, is $G_S$ ...
0
votes
0answers
39 views

Quasi-transitive decomposition of a transitive graph

Let $G=(V,E)$ be a simple digraph that is semi-complete (ie. there's at least one arc between each unordered pair of vertices) and quasi-transitive (ie. its complement is transitive). Is it true that ...
1
vote
0answers
49 views

What's the complexity of the one sink directed subgraph isomorphism problem?

I am considering trying a new approach for the subgraph isomorphism problem in my PhD, but it just seems to work well for digraphs of one sink. By working well I mean some promise of not having to ...
10
votes
3answers
339 views

The diameter of a certain graph on the positive integers

Let $G(n)$ be the graph whose vertices are the positive integers $1,2,3,4, \ldots, n$ two of which are joined by an edge if their sum is a square. Is the diameter of this graph 4 for all sufficiently ...
2
votes
0answers
34 views

Is the size of maximum matching in vertex transitive 3-uniform hyper-graph on $n$ vertices always $\Omega(n)$?

What is the best known lower bound on the size of the maximum matching in a vertex transitive $3$-uniform hyper-graph?
3
votes
1answer
64 views

Dense high-degree sub-graphs of dense graphs

Let $G$ be a graph with $n$ vertices and $m$ edges, and let $d=\lfloor\frac{m}{n}\rfloor$ be the rounded-down average-degree. A lemma that is attributed to Erdos says that $G$ has a non-empty induced ...
3
votes
1answer
99 views

Infinite non-splittable graphs

Let $G=(V,E)$ be a graph. For $v\in V$ we set $N(v)=\{w\in V:\{v,w\}\in E\}$. We say that $G$ is splittable if there are $S,T\subseteq V$ with $S\cap T=\emptyset$ and $S\cup T = V$ such that for all ...
1
vote
2answers
121 views

A certain matrix associated to graphs

I am not very familiar with graph theory, but I need some results for my work. Thus, the question is, whether the following has already been studied and where I can find it. Let $G=(V,E)$ be an graph ...
4
votes
0answers
166 views

Have topographs been studied before?

This is my first post on MO so I hope this question is suitable. I have quite a few definitions which I will need to state before my questions at the end of this post. Please let me know if anything ...
-2
votes
1answer
108 views

About structure of the set of perfect matchings of $K_{n,n}$

Are there any special properties known about the set of perfect matchings of $K_{n,n}$? Like any global structure of this set? Some natural way to partition it? Like is there some algebraic structure ...
8
votes
0answers
149 views

Lovasz's Path removal conjecture

The Lovász Path Removal Conjecture states: For any positive integer $k$, there exists a minimum positive integer $f(k)$ such that, for any two vertices $x$, $y$ in any $f(k)$-vertex-connected ...
7
votes
0answers
264 views

Does this inequality always hold?

Denote the adjacency matrix of a given undirected graph by $g$. It is an $n$-by-$n$ symmetric Boolean matrix with elements on the diagonal to be zero ($n\geq 3$). Let $g_{12}=g_{21}=g_{13}=g_{31}=1$ ...
6
votes
1answer
172 views

Isometries of some simple Cayley graphs

Consider a Cayley graph of a group $G$ with respect to a symmetric finite generating set $S$. There are some obvious candidates to isometries of this graph - for example, translation by elements of ...
2
votes
1answer
66 views

Are there non-isomorphic graphs with rationally orthogonal similar adjacency matrices?

Let $A_G,A_H$ be the adjacency matrices of two non-isomorphic graphs. Let $P$ be orthogonal matrix with rational entries. Is it possible $A_G = P^{-1}A_H P$? Paper gives algorithm for ...
5
votes
2answers
244 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
1answer
61 views

Connection between Barnette conjecture and hardness of cubic graph decomposition

Motivated by this post on cubic graphs decompositions and the connection to Barnette conjecture, I am interested in decomposing a connected bridgeless cubic graph into edge-disjoint paths of length 3 ...
1
vote
1answer
84 views

About the upper bound on the roots of the matching polynomial

Heilman and Lieb had proven that if a graph had $d$ as its maximum vertex degree then the roots of the matching polynomial are bounded from above by $2\sqrt{d-1}$. Is there a modern exposition of ...
1
vote
2answers
107 views

Nauty software package and weighted graphs

I am working with software package Nauty. It there a way to add weighted graphs in nauty software package?
3
votes
1answer
157 views

About the second largest adjacency eigenvalue of Abelian Cayley graphs

[Assume all groups are finite] One knows the general statement that the sum of the values of the character function on the generating set is an eigenvalue of a Cayley graph. But the above doesn't ...
0
votes
1answer
49 views

Maximum degree and matching number

Let $G=(V,E)$ be a finite graph. We write $\nu(G)$ for the matching number of $G$. Is there $\varepsilon > 0$ such that we have $$\frac{\nu(G)+\Delta(G)}{V(G)} \geq \varepsilon$$ for all finite ...
5
votes
0answers
116 views

$\kappa$-impediments (according to Shelah, Nash-Williams, Aharoni)

Let $\Gamma = (M, W, K)$ be a bipartite graph, that is $M, W$ are sets and $K\subseteq M\times W$. If there is an injective function $f:M\to W$ such that $f\subseteq K$ we say $f$ is an espousal and ...
1
vote
0answers
125 views

Kripke frames as classes of partitions

Here's something I've been playing with off and on for a bit; I'm curious if anyone has seen it before. For this question, a Kripke frame $K$ is a finite reflexive directed graph. (Reflexivity isn't ...
24
votes
2answers
752 views

Arranging numbers from $1$ to $n$ such that the sum of every two adjacent numbers is a perfect power

I've known that one can arrange all the numbers from $1$ to $\color{red}{15}$ in a row such that the sum of every two adjacent numbers is a perfect square. $$8,1,15,10,6,3,13,12,4,5,11,14,2,7,9$$ ...
2
votes
1answer
66 views

Generalization of Hamiltonian cycle

Let $G=(V,E)$ be a graph. For $v\in V$ we set $N(v) = \{w\in V: \{v,w\}\in E\}$. Let us say that a graph is neighborly if there is an injective function $f: V\to V$ such that $f(v)\in N(v)$ for all ...
0
votes
1answer
101 views

What is a G-Set Graph?

I keep finding references to $G$-Set graphs and I cannot find a definition anywhere. They are usually mentioned at the same time as the random graph generator "rudy," so I believe they refer to a ...
0
votes
0answers
83 views

Adjacency graph of a polyomino

Given a polyomino, the "adjacency graph" has one vertex for each tile and an edge connecting tiles which are adjacent (diagonal doesn't count). Is anything known about which graphs can be the ...
5
votes
1answer
283 views

When are (Abelian) Cayley graphs also expanders?

I want to ask the question in two parts, (1) Is there some fundamental distinguishing property between Abelian and non-Abelian Cayley graphs? (say some specific proof technique which distinguishes ...
6
votes
1answer
143 views

Probability of a graph procedure

We are going to build $K_n$ one edge at a time. Begin with the empty graph on $n$ vertices. Take a random permutation of the edges of $K_n$ and, one at a time, place the edges onto the graph (so, ...
3
votes
0answers
96 views

Hypercube edge-coloring problem

Question: Is there a pairing (a fixed point free involution) of the vertices of the $n$-dimensional cube graph, and a $2$-coloring of its edges such that the number of color changes needed to get from ...
2
votes
0answers
101 views

About the small set expansion conjecture

Given a graph $G=(V,E)$ and a $\delta > 0$ one wants to calculate $h(G,\delta)=min_{\vert S\vert \leq \delta \vert V \vert } \phi(S)$. ($\phi(S) = \frac{ E(S,\bar{S}) }{d min \{\vert S \vert , n - ...
3
votes
3answers
322 views

Aperiodic graphs

The concepts of being non-periodic and aperiodic for tilings have obvious versions for connected graphs with a countable set of vertices and a finite number of edges meeting at each vertex. A graph ...
1
vote
1answer
39 views

Linear intersection number and maximum degree

This question is inspired by a Andrew D. King's comment in Linear intersection number and coloring (not chromatic) number A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set ...
3
votes
0answers
54 views

Linear intersection number and coloring (not chromatic) number

A linear hypergraph is a pair $\pi=(X, L)$ where $X\neq \emptyset$ is a set and $L\subseteq {\cal P}(X)$ has the following properties: for $e\in L$ we have $|e|\geq 2$; if $e_1\neq e_2 \in L$ then ...