# Tagged Questions

**3**

votes

**1**answer

159 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

**1**answer

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

**0**answers

117 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

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

**2**answers

760 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

**1**answer

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

**1**answer

102 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

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

**1**answer

291 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

**1**answer

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

**0**answers

101 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

102 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

324 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

**1**answer

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

**0**answers

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

**1**

vote

**2**answers

270 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

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

**2**

votes

**1**answer

88 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

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

**1**

vote

**1**answer

49 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

82 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

142 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

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

**4**

votes

**1**answer

142 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

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

**1**

vote

**1**answer

68 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{ ...

**6**

votes

**1**answer

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

**4**

votes

**1**answer

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

**0**

votes

**1**answer

134 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

251 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

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

**0**

votes

**1**answer

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

**-4**

votes

**1**answer

71 views

### Resources to learn about hypergraphs [closed]

I am working on a project that is based on hyper graphs. Is there any resource that I could refer to understand the basics properties of hyper graphs ?

**2**

votes

**1**answer

107 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

83 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

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

**1**

vote

**0**answers

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

**3**

votes

**1**answer

148 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

117 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

143 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

35 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

44 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

168 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

67 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

60 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

102 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

117 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

185 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

157 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

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