**4**

votes

**0**answers

57 views

### “Edge Density” of Infinite Planar Graphs

Given an infinite planar graph $G$, let's denote by $\{H_1,H_2,\dots,H_m\}$ all the labeled graphs on $n$ vertices that appear as subgraphs of $G$. Also let
$$d_n=\frac{\sum_{i=1}^m \#E(H_i)}{nm}$$
...

**1**

vote

**0**answers

69 views

### “GraphI Individualization” referece request

Context: I am studying Weisfeiler Lehman method(WL method) and have clear idea about 1 and 2 dimensional WL method. I was wondering about the individualization process described below-
Defined ...

**2**

votes

**1**answer

124 views

### inequality with exponents

We are given a graph $G$, each vertex $v$ has an assigned value $\gamma_v\in [0,1]$, and it happens that for every $v$ we have $\gamma_v+\sum_{u\in \delta(v)} \gamma_u = 1$. Assume that $\sum_v ...

**2**

votes

**1**answer

99 views

### Embedding graphs into hyperbolic spaces

Do we know of a characterization as to when does a graph have a "good" embedding into a hyperbolic space? (And does having such an embedding have a spectral or wavelet analysis signature?)
I don't ...

**-4**

votes

**0**answers

163 views

### Has Frucht's theorem been successfully used in inverse Galois theory? [on hold]

Logically, one can associate to any finite extension $K$ of $\mathbb{Q}$ a directed graph describing it. Can such a graph be used together with Frucht's theorem asserting that every finite group is ...

**3**

votes

**1**answer

183 views

### Can every permutation group be realized as the automorphism group of a graph (acting on a subset of the vertices)?

By Frucht's theorem, every finite group can be realized as the automorphism group of a finite undirected graph. Because a permutation group is a finite group, it is clear that every permutation group ...

**3**

votes

**0**answers

81 views

### Does this notion of “$\mathcal{F}$-digraph” appear in the literature?

By a digraph, I mean a quiver with no multiple edges. So in particular:
Loops are okay.
An infinite set of vertexes is okay.
Furthermore, I will tend to identify each digraph with its underlying ...

**1**

vote

**0**answers

62 views

### Efficient realization of a restricted neighborhood hypergraph

In a graph $G$, the (open) neighborhood of a vertex $v$ is the set of vertices adjacent to $v$ (so vertex $v$ is excluded). The neighborhood hypergraph of $G$, denoted by $\mathcal{N}(G)$, is a ...

**-1**

votes

**0**answers

51 views

### bound on the size of a circuit [closed]

I'm currently reading a proof of the following claim from the notes http://www.cs.berkeley.edu/~sinclair/cs271/n5.pdf which can be found on the bottom of page 6. I'd like to point out i'm interested ...

**3**

votes

**2**answers

176 views

### Hedetniemi's conjecture for graphs with countable chromatic number

Are there graphs $G, H$ such that $\chi(G) = \chi(H) = \aleph_0$, but $\chi(G\times H) < \aleph_0$?

**9**

votes

**0**answers

134 views

### What algebraic structures are related to the McGee graph?

Recall that an $(n,g)$-graph is a simple graph where each node has $n$ neighbors and the shortest cycle has length $g$, while an $(n,g)$-cage is $(n,g)$-graph with the minimum number of nodes.
The ...

**1**

vote

**1**answer

62 views

### Categorical product of graphs and chromatic number

Let $(G_i)_{i\in I}$ denote a family of simple, undirected graphs (finite or infinite). Let $\prod_{i\in I}G_i$ denote their categorical product. Why do we have the inequality
$$\chi(\prod_{i\in ...

**1**

vote

**0**answers

76 views

### 3-regular (cubic) graph with adjacency eigenvalue 1

Suppose $A\in\{0,1\}^{n\times n}$ is the adjacency matrix of a 3-regular (cubic) graph $G=(V,E)$; that is, all $n$ vertices $v\in V$ in the graph have three neighbors.
Is there a nice necessary ...

**2**

votes

**2**answers

124 views

### Detecting HNN-Extension and free products with amalgamation

This question is partly connected with the following Connection between Stalling's end theorem and Seifert-van Kampen Theorem.
By Stalling's Theorem a group with more than one end splits over a ...

**3**

votes

**1**answer

70 views

### Good broad review of agent-based modeling? [closed]

Trying to find some good review of agent-based models and networks, specifically models that are defined by a graph of interacting nodes, that covers analysis of collective behavior based on model of ...

**1**

vote

**0**answers

66 views

### Obtaining a quasi-isometry of the 'boundary'

It is well-known that a quasi-isometry induces a homeomorphism on the space of ends of say a locally finite graph for simplicity. Clearly the converse is not true. In other words the concept of ends ...

**1**

vote

**1**answer

198 views

### Can we estimate the probability $\mathbf{P}(a-k|a - b) $ on a random graph?

Let $G=(V,E)$ be an undirected random graph such that
$V$ is the set of nodes, and $E$ is the set of edges
Assume the ground graph $G$ is sparse enough, for example, $\frac{|E|}{|V|}= c \in [10, ...

**0**

votes

**1**answer

88 views

### Reference request: Strong Connectivity and the Incidence Matrix

Question: What would be a good reference for characterizations of strong connectivity of a digraph in terms of its incidence matrix?
Details: Consider a digraph $(V, E)$ with vertex set
$$V = ...

**9**

votes

**2**answers

305 views

### Is every metric space quasi-isometric to a graph?

I've proved that if $(X, d)$ is a geodesic metric space then there exists a graph which is quasi-isometric to $X$...during this proof I've precisely used the fact that given two point in $X$ there ...

**5**

votes

**0**answers

68 views

### Diameter of the modified bubble-sort graph

The modified bubble-sort graph is the Cayley graph $Cay(S_n,S)$ of $S_n$ generated by $n$ cyclically adjacent transpositions. Thus $S = \{ (1,2),(2,3),\ldots,(n,1)\}$. I was wondering whether the ...

**0**

votes

**1**answer

74 views

### Forbidden Tripartite Graphs

I was looking at extremal graph theory. I have understood the proofs of upper bounds for the Zarankiewicz problem which basically states: What can you say about the edges of a graph with $n$ vertices ...

**1**

vote

**0**answers

14 views

### Properties of Optimal k-Tour Spanners

Let the edge set of a Optimal k-Tour Spanner of a graph $G$ be equal to the edges of $G$ that lie on at least one optimal tour through exactly $3<k<n$ distinct vertices of $G$.
I would like ...

**1**

vote

**0**answers

100 views

### Classification of Automorphism set of a Regular graph

Let $A$ be the adjacency matrix of an $r$-regular graph $G$ with $n$ vertices (Not complete or cycle graph) . Also, let $Aut(G)$ be the set of all its automorphisms (i.e. set of permutation ...

**10**

votes

**3**answers

444 views

### Self-Similar Graphs

Many fractals can be generated using and infinite sequence of graphs. For example, Sierpinski's Gasket could be generated by the following sequence of graphs.
Many definitions of fractal dimensions ...

**17**

votes

**0**answers

491 views

### Reference request: Parallel processor theorem of William Thurston

Sometime in the 1980's or 1990's, Bill Thurston proved a theorem regarding the existence of a universal parallel processing machine, using a certain class for such machines having finite deterministic ...

**3**

votes

**0**answers

61 views

### Relationship of Weisfeiler-Lehman algorithm to weak isomorphism of coherent algebras

A coherent algebra is a matrix algebra (over $\mathbb{C}$) closed under conjugate transpose and Schur (entrywise) product, and that contains the identity matrix $I$ and all ones matrix $J$. Given ...

**0**

votes

**2**answers

59 views

### Connectivity of weighted graph and zero Laplacian eigenvalues

Given an undirected graph $G$, and let $V$ denote its set of vertices and $E$ its set of edges. Suppose that there are no edges connecting the same vertex, and no more than one edge connecting any ...

**5**

votes

**1**answer

300 views

### Terminology in combinatorics

I met the following two combinatorial concepts during a study outside of combinatorics. I am wondering if there are common terminologies in combinatorics.
A finite graph $G$ has the following ...

**1**

vote

**0**answers

35 views

### Modularity in a graph - definition of the random component

This question concerns the definition of modularity in a graph.
Consider a simple, undirected, unweighted graph $G$ with vertices in set $V$ and edges in set $E$ . Between any two vertices there is ...

**6**

votes

**1**answer

68 views

### Analysis of the Laplacian of a random bipartite graph

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take ...

**4**

votes

**2**answers

192 views

### A generously vertex transitive graph which is not Cayley?

A graph is vertex transitive if $x \mapsto y$ by an automorphism.
A graph is generously vertex transitive if $x \mapsto y \mapsto x$ by an automorphism.
Simple facts:
GVT $\rightarrow$ unimodular. ...

**2**

votes

**0**answers

221 views

### Partitioning graph for Graph Isomorphism

Motivation: I am studying graph isomorphism problem. I am trying to construct a partitioning method to reduce search cases .
Construction:
$G$ is a $r$ regular graph, $k$ connected( not a complete , ...

**0**

votes

**1**answer

125 views

### Decomposition of a regular graph and connected subgraphs

I have asked almost same question earlier. I have been told that my question was poorly written, so I am trying to write it more clearly in this post. Also, this time I would be a little different in ...

**2**

votes

**0**answers

56 views

### Even cycle constrained edge coloring

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every $2t$ simple cycle where $t\in\Big\{1,\dots,2\Big\lfloor\frac{n}2\Big\rfloor\Big\}$ contains atleast $t+1$ ...

**5**

votes

**0**answers

94 views

### Does squaring a directed random graph more than double its out-degree?

As far as I know, it is an unsolved question
whether or not this is true:
If $G$ is a directed an oriented graph, $G^2$ always has some node whose outdegree is at least
double that of its ...

**0**

votes

**0**answers

71 views

### A constrained minimum edge coloring

Is minimum number of colors needed to color edges of complete graph $K_n$ so that every even simple cycle contains at least one color assigned to odd number of edges at most $\beta n$ where ...

**2**

votes

**2**answers

53 views

### Minimal edge color on constraints

Is minimum colors needed to assign colors to edges of complete graph $K_n$ so that every even simple cycle contains an odd number ($>1$) of colors much larger than $(\log n)^\beta$ or ...

**1**

vote

**0**answers

97 views

### Efficiently counting all paths of length n in a graph with vertex visitation contraints [closed]

I have a graph G with two classes of vertices. The first class represents no resource limitation entities and can be visited an unlimited number of times in any path traversal. The second class of ...

**3**

votes

**2**answers

134 views

### “Nice” and “nasty” partitions in graphs

Let $G=(V,E)$ be a simple, undirected graph, that is $V$ is a set and $E \subseteq [V]^2 = \{\{v,w\}: v,w \in V \land v\neq w\}$.
For $v\in V$ and $S\subseteq V$ we set $$N(v,S) = \{w\in S: \{v,w\} ...

**1**

vote

**0**answers

32 views

### One sided Satisfactory Partition problem

The Satisfaction Partition problem is to decide if a graph has a vertex partition (U,V) into non empty parts where each vertex has as many neighbours in its part as in the other part. This problem is ...

**1**

vote

**0**answers

364 views

### Possibility of Disconnected Subgraphs of a $k$ Connected $r$ regular Graph under a given condition

Context: Given a adjacency matrix A of a $r$-regular graph $G$ (not complete graph $K_{r+1}$) . $G$ is $k$ connected.
The matrix A can be divided into 4 sub-matrices based on adjacency of vertex $x ...

**1**

vote

**0**answers

34 views

### Weak law for component count of Erdos-Renyi random graphs

Penrose and Yukich derive a weak law for functionals of binomial point processes, which implies a law of large numbers for the component count of random geometric graphs. Do similar results exist for ...

**8**

votes

**2**answers

232 views

### Dividing the edges and diagonals of a polygon among disjoint sub-polygons

Let $P$ be a convex $n$-gon ($n$ is odd and $n \geq 5$).
Determine the smallest $m$ such that all edges and diagonals of $P$ can be covered by the edges
of $m$ convex sub-polygons of $P$ which ...

**1**

vote

**0**answers

98 views

### From Planar Graphs To Tangent Circles

I have a conjecture:
"For each planar graph with vertices $V_1, V_2,\ldots, V_n$ there exist disjoint circles $w_1,w_2,\ldots,w_n$ in the plane, such that for every $i,j$, $w_i$ is tangent to $w_j$ ...

**12**

votes

**3**answers

1k views

### A question on representation of graphs

Take a complete graph $K_n$. You want to assign a vectors from $\Bbb F_2^d$ to every edge such that sum of vectors in every simple cycle does not sum to $0$ vector. The question is what is minimum $d$ ...

**5**

votes

**1**answer

153 views

### Modification of matching

Suppose i have an $n \times n$ random bipartite graph and suppose that i repeat the following process $n$ times. At the start (stage 1) each edge is selected independently with probability $p(n)$, and ...

**2**

votes

**1**answer

75 views

### Images of interval edge coloring

I found out the definition of interval edge colorings, concept put by Kamalian in various papers but could not find a graph depicting an example. Where can I find pictures of explicit examples of ...

**8**

votes

**1**answer

213 views

### Smallest strongly regular graph whose automorphism group is not vertex transitive?

I'm looking for a small strongly regular graph whose automorphism group is not vertex-transitive.
This answer to a different question shows that the Chang graphs on 28 vertices are such graphs. Is ...

**1**

vote

**0**answers

134 views

### Cayley graphs with special subgraphs and some related problems

I asked some questions about finite Cayley graphs with special type of subgraphs which has been answered by Dear Prof. Godsil. It can be seen in the MO page with address:
Cayley graphs and its ...

**1**

vote

**0**answers

58 views

### Interpreting (Fiedler) spectral bisectioning

I would appreciate help on how to interpret the results of spectral bisectioning of a graph.
Given a $G=(V,E)$ with size $N$ represented by $Q$ its Laplacian matrix where the eigenvalues are ordered ...