**4**

votes

**4**answers

347 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

**1**answer

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

**2**

votes

**0**answers

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

**2**

votes

**1**answer

137 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$ ...

**4**

votes

**1**answer

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

**2**

votes

**1**answer

41 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

**1**answer

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

**7**

votes

**1**answer

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

**1**

vote

**1**answer

49 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

**0**answers

43 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

**0**answers

58 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

**3**answers

370 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

**0**answers

50 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

**1**answer

66 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

**1**answer

107 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

**2**answers

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

**6**

votes

**0**answers

257 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

**1**answer

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

**9**

votes

**1**answer

188 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

**0**answers

272 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

**1**answer

194 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

**1**answer

69 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

**2**answers

331 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

**1**answer

76 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

**1**answer

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

**3**

votes

**1**answer

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

**1**

vote

**1**answer

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

**6**

votes

**0**answers

121 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

**0**answers

135 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

**2**answers

815 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$$
...

**3**

votes

**1**answer

76 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

**1**answer

107 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

**0**answers

88 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

**1**answer

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

**7**

votes

**1**answer

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

**4**

votes

**0**answers

120 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

**0**answers

110 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

**3**answers

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

**2**

votes

**1**answer

47 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

**0**answers

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

**1**

vote

**2**answers

302 views

### Independence Number of Graphs

Suppose $\alpha(G)\leq\alpha(H)$ where $G$ and $H$ are graphs, and $\alpha(.)$ is the independence number of graph. Is the following statement true?
$\alpha(G\boxtimes G) \leq \alpha(H\boxtimes H)$ ...

**4**

votes

**1**answer

106 views

### Edges of $K_n$ are colored, connected few-colored subgraph is needed

Assume that all edges of a complete graph $K_n$ are colored in $k$ colors. We want to choose $m$ colors so that the graph formed by edges of chosen colors is connected. It is always possible if $m\geq ...

**3**

votes

**1**answer

102 views

### Relationship of clique, independence, and chromatic numbers

For any graph $G=(V,E)$ let $\bar{G}$ be the complement graph. Is $$\text{inf}\big\{\frac{\omega(G)+\omega(\bar{G})}{\chi(G)} : G \text{ is a finite graph}\big\}$$ known? If not, what lower bounds are ...

**3**

votes

**2**answers

136 views

### regular polyhedra (and polytopes) in hyperbolic geometry, and generalisations

While there exist regular tesselations of the hyperbolic plane with arbitrary regular polygons, there are no new regular polyhedra in hyperbolic (3D) space. This being quite trivial, it is probably ...

**2**

votes

**1**answer

54 views

### Graph of bounded continous functions with distance 1

Let $V = \{f:[0,1]\to \mathbb{R}: f \text{ is continuous}\}$ and consider the metric that is defined for $f,g\in V$ by $$d(f,g) = \max\{|f(t)-g(t)|: t\in [0,1]\}.$$
We set $E = \{\{f,g\}: f,g \in ...

**2**

votes

**0**answers

93 views

### the choosing of an independent set in a specific $k$-partite graph

Let $k\geq2$ be an integer, a graph $G=(V,E)$ is called $k$-partite if $V$ admits a partition into $k$ classes such that every edge of $G$ has its ends in different classes: vertices in the same class ...

**7**

votes

**1**answer

151 views

### When is the tensor product of two graphs planar?

Given two graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$, the tensor product of $G$ and $H$ is the graph $G \times H = (V,E)$, where $V=V_1 \times V_2$ is the Cartesian product of the $V_i$ and
$ (u,v) \ E \ ...

**0**

votes

**0**answers

44 views

### Weighted eigenvector-entry sums of bipartite graphs

Let $\lambda_m$ denote the $m$-th eigenvalue of the adjacency matrix $A$ of a bipartite graph $G$ of order $N$ and ${\bf v}_m$ the normalized eigenvector corresponding to $\lambda_m$. I am looking for ...

**5**

votes

**1**answer

151 views

### Hadwiger's conjecture for coloring number instead of chromatic number

For any graph $G=(V,E)$, the coloring number $\text{Col}(G)$ is defined to be the smallest cardinal $\kappa$ such that there is a well-ordering $\leq$ on $V$ such that for every vertex $v\in V$ we ...

**3**

votes

**0**answers

30 views

### Isomorphic Hadwiger graphs of connected infinite graphs

Let $G$ be a graph, then we define its Hadwiger graph $\textrm{Hadw}(G)$ in the following way:
$V(\textrm{Hadw}(G)) = \{S\subseteq (V(G): S\neq \emptyset\textrm{ and } S \textrm{ is connected}\}$;
...