**0**

votes

**0**answers

89 views

### When does the normalized graph Laplacian have eigenvalue 1?

Let $G= (V,E)$ be a finite, undirected and unweighted graph with $V = \{v_1,\ldots, v_n\}$. Denote by $d_i$ the degree of $v_i$, i.e. the number of vertices that are adjacent to $v_i$. Let $A$ be the ...

**5**

votes

**1**answer

200 views

### Does the minor graph of graphs on $\mathbb{N}$ have an uncountable independent set?

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. We write $V(G) := V$.
If $S, T$ are disjoint subsets of $V(G)$ we say that ...

**6**

votes

**1**answer

295 views

### Uncountably many countable graphs with no homomorphism between them

By a graph I mean a pair $G = (V, E)$ where $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\}: a\neq b \in V\}$. A graph homomorphism between graphs $G, H$ is a map $f:V(G)\to V(H)$ such ...

**1**

vote

**0**answers

56 views

### Proper edge colorings with no bi-colored 5-paths

Consider you want to properly edge color a graph such that it has no bi-colored cycle. Denote by $\alpha'(G)$ the least number of colors required to color the edges of $G$ in such a way.
It is well ...

**2**

votes

**1**answer

130 views

### Is there some quantitative version of interlacing of eigenvalues of a matrix under rank-1 update?

Given a real symmetric matrix $A$ and a vector $v$ of the same dimension we know that the eigenvalues of $A + vv^T$ are left interlaced by the eigenvalues of $A$.
But do we have any quantitative ...

**7**

votes

**1**answer

116 views

### Infinite graphs with “similar” Hom-sets

Let $G,H$ be infinite simple undirected graphs with the property that for any graph $X$ we have $|\text{Hom}(X,G)| = |\text{Hom}(X,H)|$. Does this imply that $G$ is isomorphic to a subgraph of $H$, ...

**1**

vote

**0**answers

35 views

### Find paths in a graph that any 2 vertices can be reached through N of them

Given a undirected weighted graph.
I would like to find a finite set of paths (consecutive vertices and edges)
each shorter than L
any two vertices can be reached through at most N(in my case N=4) ...

**2**

votes

**0**answers

122 views

### Polynomial-time algorithm solving approximately a generalization of the travelling salesman problem

Take a graph $G$ and a number of sets of nodes of $G$. The problem is to find the shortest path passing through at least one node in each node set. If each node set consists of only one node, the ...

**7**

votes

**1**answer

117 views

### Does the Tutte polynomial of iterated cone graphs detect isomorphism?

Let $T_G(x,y)$ denote the Tutte polynomial of a graph. Of course we may have $T_G(x,y) = T_H(x,y)$ for $G$ and $H$ non-isomorphic graphs.
Now let $c(G)$ denote the cone graph of $G$, i.e., the graph ...

**1**

vote

**1**answer

62 views

### Graph classes which are not perfect but the stability number = clique cover numer?

I have a result for graphs whose stability number=clique cover number, which naturally includes the perfect graphs, but I'm curious about if there are other known and well-definable graph classes ...

**7**

votes

**2**answers

147 views

### Isomorphism problem on the class of induced subgraphs of a hypercube

A problem that I am currently studying translates to the problem of deciding whether two induced subgraphs of the hypercube $Q_k$ are isomorphic.
Now it feels to me that this class of graphs is "too ...

**0**

votes

**0**answers

24 views

### Cardinality of maximum independent set for a given degree distribution

Consider undirected graph $G(V,E)$. Assume that $f_n(k)$ be the probability mass function of degree of a vertex in $G$. Further, assume that $f_n(k)$ is an strictly decreasing function of $k$ with ...

**-2**

votes

**1**answer

75 views

### How does deletion-contraction affect chromatic number? Can it increase chromatic number? [closed]

Question: In graph theory, contracting an edge or deleting an edge are basic operations in many topics such as graph minors or Wagner's theorem on planar graphs. And I'm interested in how these ...

**3**

votes

**0**answers

28 views

### Minimality of maximal expansions of a hypergraph cover

This is a follow-up question to Maximal expansions of strongly minimal covers of hypergraphs.
Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E ...

**2**

votes

**1**answer

27 views

### Maximal expansions of strongly minimal covers of hypergraphs

Let $H = (V,E)$ be a hypergraph, that is $V$ is a set and $E \subseteq {\cal P}(V)$. We assume $\bigcup E = V$. Moreover we assume that every $e\in E$ is contained in some maximal member $e'\in E$ ...

**8**

votes

**3**answers

273 views

### Borel coloring of a graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$

The following question was asked in a comment by Joel David Hamkins in Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$.
Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. ...

**3**

votes

**1**answer

254 views

### Graph on the set of all functions $f:\mathbb{N}\to\mathbb{N}$

Let $V$ be the set of all functions $f:\mathbb{N}\to\mathbb{N}$. Let two distinct functions $f,g:\mathbb{N}\to\mathbb{N}$ form an edge if and only if they differ in exactly one input $n\in\mathbb{N}$.
...

**12**

votes

**2**answers

320 views

### Graph $G$ with $\omega(G) = 2$ but $\chi(G) \geq \aleph_0$

Given an infinite cardinal $\kappa$, is there a graph $G$ that has no clique consisting of more than 2 points, but $\chi(G) = \kappa$?

**5**

votes

**0**answers

46 views

### Perfect matchings of a regular, uniform, partite hypergraph

This is in relation to the question here. What, if any, are the known conditions for the existence of a perfect matching for a $r$-regular, $r$-uniform, $r$-partite hypergraph. I specifically ...

**6**

votes

**1**answer

135 views

### Regular epimorphisms in the category of simple undirected graphs

Let $\textbf{Grph}$ be the category whose objects are graphs $G = (V,E)$ such that $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We sometimes write $E(G)$ for ...

**7**

votes

**1**answer

301 views

### Under $\neg CH$, have countable unions of rationally independent numbers inner measure zero?

In their 1943 paper On non-denumerable graphs, Erdos and Kakutani suggest as likely the following proposition.
(EK*) Suppose CH fails and $\lbrace M_n : n \in \omega \rbrace$ is a countable family of ...

**23**

votes

**1**answer

1k views

### Algebraic proof of Five-Color Theorem using chromatic polynomials by Birkhoff and Lewis in 1946

I'm guessing everyone is familiar with Four Color Theorem which was proved by Appel and Haken using computers. A weaker version of this theorem is Five Color Theorem which states that a planar graph ...

**5**

votes

**1**answer

254 views

### A claim from “Graph minors - a survey” by Robertson and Seymour

Can someone give me a proof sketch for this:
Let $\mathscr{P}_n$ be the set of all graphs which do not contain a path on $n$ vertices as a subgraph. Define the type of a graph inductively as: the type ...

**1**

vote

**1**answer

1k views

### Does this linear algebra construction based on a graph have a name, and where has it been studied?

In the paper Kochen-Specker set with seven contexts by Lisonek, Badziag, Portillo and Cabello, the following construction is used :
Question : Have such constructions been used elsewhere, and if so ...

**0**

votes

**1**answer

75 views

### Connectedness of the complements of the connected subsets

EDIT: My original foolish version was instantly destroyed by Dylan Thurston; it consisted of questions 1 & 2 below. Thus now only new question 0 remains to be answered.
Let $\ X:=M^n\ $ be a ...

**2**

votes

**2**answers

151 views

### Probability of relations in network

Imagine, i have a predicate $\text{friends}(x_1, x_2)$ and I know that $p(\text{friends}(x_1, x_2)) = p_2$. If I generate a world of $n$ people ($x_1$ to $x_n$), I expect there to be $\binom{n}{2}p_2$ ...

**1**

vote

**0**answers

92 views

### Are back edges mandatory in Ford Fulkerson algorithm?

Consider the algorithm of Ford Fulkerson where, for each iteration, you add flow along a path equal to the maximum residual capacity along this path.
Does it exist, for every network, a choice of ...

**3**

votes

**1**answer

97 views

### Average degree of neighbors in a simple graph (-> Friendship paradox)

Given a simple, undirected graph $G=(V,E)$ and $v\in V$ we set $N(v) = \{w\in V:\{v,w\} \in E\}$ and $\text{deg}(v) = |N(v)|$.
The average degree of the neighbors of a vertex $v$, or $\text{ad}(v)$, ...

**1**

vote

**1**answer

97 views

### Does every connected vertex transitive graph on $n$ vertices (except for $C_n$) have minimum feedback vertex set of size $\Omega(n)$?

Feedback vertex set is a set of vertices whose removal leaves an acyclic graph.
It is known that every vertex transitive graph on $n$ vertices has minimum vertex cover of size $\Omega(n)$. It is also ...

**3**

votes

**1**answer

121 views

### Regular and extremal monomorphisms in the category of graphs

Let $\textbf{Grph}$ be the category whose objects are graphs $G = (V,E)$ such that $V$ is a set and $E \subseteq \mathcal{P}_2(V) := \{\{a,b\} \subseteq V: a\neq b\}$. We sometimes write $E(G)$ for ...

**4**

votes

**2**answers

178 views

### Vertex expansion of the Hamming graph

Let $G$ be a graph, and for every $S \subseteq V$, let $N(S)$ denote the neighborhood of $S$. The vertex expansion of $G$ is
$$ \min_{S\subseteq V, |S|\le |V|/2} \left\{ \frac{|N(S)|}{|S|} ...

**1**

vote

**1**answer

173 views

### Random graphs with boundary in a game (Tsuro)

Suppose we have an $n \times n$ board and we have $n^2 - 1$ square tiles. These tiles consist of a 8 vertices, two on each edge, and every vertex is connected to precisely one other vertex. These ...

**5**

votes

**1**answer

168 views

### Graph of graph homomorphisms

For (finite or infinite) undirected, simple graphs $G, H$, let
$V_{\text{Hom}} = \{f:G\to H:f\text{ is a graph homomorphism}\}$, and
$E_{\text{Hom}} =\big\{\{f,g\}\subseteq V_{\text{Hom}}: ...

**3**

votes

**1**answer

180 views

### Seymour's second neighborhood conjecture

Does anyone out there know if Seymour's second neighborhood conjecture is still open? if not, I would appreciate any references.

**2**

votes

**0**answers

49 views

### Decomposing a weakly chordal graph into disjoint union of co-chordal graphs

A graph G is said to be co-chordal if it is $\bar C_n$-free for any $n \ge 4$. It is weakly chordal if it is $C_n$ and $\bar C_n$ free for all $n\ge 5$. Assume that the induced matching number of $G$ ...

**5**

votes

**0**answers

62 views

### Approximating a max-cut's intersection with other cuts

(This is a cross-post from the Theoretical Computer Science Stack Exchange.)
For the purposes of this question, a cut in a graph $G$ is the edge-set $\delta (S)\subseteq E(G)$ between some vertex-set ...

**4**

votes

**1**answer

106 views

### Example to show pairwise crossing number is not equal to crossing number

A common point of two edges in a graph drawing that is not an incident vertex is called a crossing.
The crossing number $cr(G)$ is defined to be the minimum number of crossings in any drawing of ...

**5**

votes

**1**answer

128 views

### lower bound on A(k,4,floor(k/2))

A(k,4,r) is the independence number of the Johnson graph J(k,r).
What is the best known asymptotic lower bound on A(k,4,floor(k/2)) ?
I only obtained ...

**11**

votes

**3**answers

315 views

### Models for graphs representing real-life networks

I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks).
I will be thankful for answers ...

**1**

vote

**1**answer

89 views

### Linear algebra formulation for colored node graph isomorphism

(Please see a few paragraphs below by what I mean by “colored node graph isomorphism”.)
Some basic definitions for completeness:
Given two graphs $G_1=(V_1, E_1)$ and $G_2=(V_2, E_2)$ the graph ...

**4**

votes

**0**answers

134 views

### Connection between connectivity and cohesion of a graph

Tutte [1] proved that, for every $3$-connected graph $G$ and vertices $u$ and $v$, there exists a nonseparating $uv$-path.
A graph $G$ is $t$-cohesive if $G$ is connected, has at least two vertices, ...

**3**

votes

**1**answer

105 views

### Expected number of leaf nodes in some theoretical graph models

If a leaf node of a graph refers to a node having the degree of 1, how can one compute the expected number of leaf nodes of:
(A) a random graph (e.g., Erdos-Renyi graph),
(B) a small-world graph ...

**1**

vote

**0**answers

71 views

### Probabilistic proof for expander existence [closed]

I am new to probabilistic proofs and trying to understand them better. Apparently, a common probabilistic proof focuses on the existence of expanders (eg. vertex expanders).
I've been using the search ...

**21**

votes

**2**answers

2k views

### An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...

**1**

vote

**1**answer

238 views

### Limit Group decomposition

I would need a clarification about a statement in the article Limit groups and groups acting freely on $\mathbb{R}^n$-trees by Vincent Guirardel.
First recall that a limit group is a finitely ...

**3**

votes

**1**answer

102 views

### Create matrix containing values in [0,1] where sum of all diagonals and anti-diagonals is fixed

The problem I am facing sounds at first glance pretty simple. However, as very often, it seems more complicated than I first assumed:
I want to calculate a matrix $P = (p_{j,k}) \in \mathbb{R}^{n ...

**5**

votes

**0**answers

103 views

### A digraph related to permutations

A finite sequence of distinct real numbers of length $n$ determines a linear order of $\{1,\ldots,n\}$, by mapping position to rank; call this the permutation of the sequence.
Consider the following ...

**4**

votes

**0**answers

143 views

### What is known about the complexity of this covering problem?

Let $G=(V,E)$ be a graph. A vertex set $X\subseteq V$ is called critical if $X\neq\emptyset$ and no vertex in $V\setminus X$ is adjacent to exactly one vertex in $X$. The problem is to find a vertex ...

**2**

votes

**0**answers

63 views

### Edge-disjoint path-systems in infinite digraphs

Let $ D=(V,A) $ be a directed graph without backward-infinite paths and let $ \{ s_i \}_{i<\lambda},U \subset V $ where $
\lambda $ is some cardinal. Assume that for all $ u\in U $ there is a ...

**2**

votes

**0**answers

44 views

### Mappings between adaptive networks and Markov processes

Are there any known mappings between adaptive networks models (i.e. graph model representations of networks where the internal vertex dynamics and connectivity topology can change subject to specific ...