**1**

vote

**1**answer

60 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

122 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

137 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

842 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

80 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

108 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

89 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

338 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

197 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

124 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

335 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

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

**4**

votes

**0**answers

60 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

309 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

106 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

148 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

56 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

95 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

152 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

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

**4**

votes

**0**answers

33 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}\}$;
...

**2**

votes

**1**answer

73 views

### Hadwiger-Nelson problem in higher dimensions

Given a positive integer $n\in \mathbb{N}$ we define the Hadwiger-Nelson graph $\text{HN}_n$ by
$V(\text{HN}_n) = \mathbb{R}^n$;
$E(\text{HN}_n) = \{\{v_1, v_2\}: v_1, v_2 \in \mathbb{R}^n \text{ ...

**7**

votes

**1**answer

252 views

### A variant to the Hadwiger-Nelson problem

Consider the following graph $G=(V,E)$ where $V=\mathbb{R}^2$ and $E = \{\{x,y\}: x,y \in \mathbb{R}^2 \text{ and } |x-y|\in \mathbb{Q}\}$.
What is $\chi(G)$?
(This is a variant of the ...

**5**

votes

**1**answer

113 views

### Countable hypo-hamiltonian graph

If $G = (V,E)$ is a graph, then a $\omega$-path is an injective map $p:\omega\to V$ such that $\{p(k),p(k+1)\}\in E$ for all $k\in \omega$. In a similar fashion, we define a $\mathbb{Z}$-path.
Is ...

**2**

votes

**1**answer

141 views

### Ore's theorem for countable graphs

Ore's theorem states that in a finite graph $G$ with $|V(G)|=n$, there is a Hamiltonian path, provided that the sums of the degrees of 2 distinct, non-adjacent vertices is $\geq n$.
For countable ...

**3**

votes

**1**answer

288 views

### How many hamiltonian paths can be removed from a complete directed graph before it becomes disconnected?

The question started from a problem brought home by a friend's 5th grader: "How many ways you can arrange 5 people sitting around a round table so that the people sitting to the left of any person are ...

**2**

votes

**2**answers

170 views

### Upper bounds on the edge clique cover number on special graph classes

An edge clique cover of an undirected graph $G$ is a set of cliques of $G$ such that every edge of $G$ is an edge in at least one clique in the set. The edge clique cover number $\theta(G)$ is the ...

**1**

vote

**2**answers

107 views

### Counting the orderings of outward-directed trees where the degree of each vertex is $2$

Let $T$ be a connected directed tree with the following properties:
The degree of each vertex of $T$ is at most $2$ (I am sure there is a name for such a graph but I do not know it).
$T$ has a ...

**2**

votes

**1**answer

108 views

### Network flows with shared capacities

Suppose we have a flow network, with capacity constraints on weighted sums of arc flows, such as:
$$2 f(1, 2) + 3 f(4, 5) + f(3, 7) \leq 10,$$
where $f(1, 2)$ denotes the flow through arc $(1, ...

**0**

votes

**1**answer

98 views

### A question about graphs not having non-trivial automorphisms [closed]

Let call a simple graph (not containing neither loops, nor multiple edges) "prime", if it has no non-trivial automorphisms, i.e. graph that has only "identity" automorphic transformation. I cannot ...

**5**

votes

**0**answers

205 views

### When does a “stable” assignment of buyers into goods exist?

Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...

**2**

votes

**0**answers

104 views

### Discrete p-Laplacian

One of the definitions of the discrete (weighted) $p$-Laplacian is the following:
$$\Delta_{p,w}u(x):=\sum_y |u(y)-u(x)|^{p-2}(u(y)-u(x))w(x,y).$$
Consider the one dimensional case. Then the free ...

**5**

votes

**2**answers

192 views

### Condition(s) for the full autormophism group $\operatorname{Aut}(C(G, S))$ of the Cayley graph of $G$ to be isomorphic to $G$

If $\Gamma = C(G, S)$ is the (undirected) Cayley graph of a finite group $G$ with generating set $S$, then $G \le \operatorname{Aut}(\Gamma)$, the "full" automorphism group of $\Gamma$.
When is ...

**3**

votes

**2**answers

137 views

### Matching polynomials and Ramanujan graphs

Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts?
A $d-$regular graph is said to be called Ramanujan if its adjacency ...

**2**

votes

**2**answers

154 views

### Term for vertex connected to every other vertex in a graph

Do you know a good common term for the operation of connecting a new vertex v to every vertex in a graph G (or a term for such vertex v)?
The ones I know give me poor search results:
a nice word ...

**0**

votes

**0**answers

38 views

### Least square problems with binary variables

I want to solve the heat equation $T_t(x,t) = - L_x . T(x,t) + F(x,t)$ in an edge-weighted graph where $L_x = \sum_i x_i e_{ij}$ is weighted Laplacian matrix of the graph. Then I conclude to the ...

**0**

votes

**0**answers

57 views

### Discrete bi-Laplacian

I was wondering whether there exists any kind of literature on the the powers of the discrete Laplacian, in particular the the discrete bi-Laplacian, possibly with weights on the edges.
In particular ...

**8**

votes

**1**answer

175 views

### Is the Cayley graph of Thompson's group isolated in the space of vertex-transitive graphs?

Consider Thompson's group (the one commonly referred to as $T$), which is finitely presentable. Consider the Cayley graph, but then forget the coloring and direction on edges. So now we just have an ...

**7**

votes

**0**answers

68 views

### Approximation of the effective resistance on Cayley graph

Let $\Gamma$ be a finitely generated group, and denote by $G$ the Cayley graph of $\Gamma$. Denote by $d_R$ the resistance distance metric on this graph. The resistance distance metric between the ...

**0**

votes

**0**answers

71 views

### Confusion about reduction counting vertex covers to counting cycle covers

Cross-posted from cstheory
This confuses me.
One easy case of counting is when the
decision problem is in $P$ and there are no solutions.
A lecture show that the problem of counting the number of ...

**5**

votes

**0**answers

104 views

### What's the variance in the Six Degrees model?

Recall the six degrees of Kevin Bacon game. You can even play the game at The Oracle of Bacon, and their search works via Breadth First Search.
I interpret the punchline as saying that if I start ...

**3**

votes

**1**answer

129 views

### Directed Hypercube Minimal Cuts

If $[n]:=\{1,2,\ldots, n\}$ for some $n\in\mathbb{N}$, then the hypercube digraph of dimension $n$, denoted $H_n$, is the graph whose set of vertices is the power-set $\wp([n])$ where two vertices ...

**6**

votes

**2**answers

209 views

### Geometric dominating set: NP-complete?

Let $G=(V,E)$ be a geometric graph, a graph embedded in the plane whose edge lengths are
the Euclidean distance between its endpoint vertices.
Say that a set of vertices $D \subseteq V$ is a geometric ...

**4**

votes

**2**answers

206 views

### Statistics of strongly connected components in random directed graphs

I'm interested in the statistics of strongly connected components in random directed graphs. However, I'm unable to find any results on this, partly because I don't know the terminology to search for.
...

**4**

votes

**1**answer

96 views

### Are there 2-connected regular graphs whose maximum matching leaves 3 vertices uncovered?

I'd like to use Corollary 5 of a paper by Hell & Kirkpatrick on graph packings to obtain an NP-hardness result. They want a 2-vertex-connected graph $F$ such that every matching in $F$ leaves at ...

**3**

votes

**1**answer

95 views

### When the vertex covering number is smaller than the chromatic number

For any graph $G=(V,E)$ let $\tau(G)$ be the minimum cardinality of a vertex cover of $G$.
As noted here, we have $\tau(G) \geq \chi(G) - 1$ for all finite graphs $G$. I'm interested in graphs $G$ ...

**1**

vote

**1**answer

129 views

### Proof of closed walk generating function identity

In 'Spectral Conditions for the Reconstructibility of a Graph' Godsil and McKay give a short proof of an identity (Lemma 2.1) that relates the generating function for the number of closed walks ...