# Tagged Questions

**2**

votes

**1**answer

280 views

### Is there a graph with 99 vertices in which every edge belong to a unique triangle and every nonedge to a unique quadrilateral?

99-Graph:Is there a graph with 99 vertices in which every edge(i.e. pair of joined vertices) belong to a unique triangle and every nonedge(pair of unjoined vertices) to a unique quadrilateral?

**2**

votes

**1**answer

53 views

### Graph construction to double coloring & Hadwiger number

For any graph $G$ let $\eta(G)$ be the Hadwiger number of $G$.
Is there for every graph $G$ a graph $2G$ such that
-- $\chi(2G) = 2\chi(G)$, and
-- $\eta(2G) = 2\eta(G)$?
For each one of the above ...

**0**

votes

**1**answer

64 views

### Additivity of genus of a graph [duplicate]

Let $G$ be a finite simple undirected graph. Suppose there exist subgraph $G_1,G_2,\dots,G_n$ of $G$, such that $E(G_i)\cap E(G_j) = \emptyset$ and $|V(G_i)\cap V(G_j)| \leq 2$, for $i\neq j$. Then, ...

**0**

votes

**0**answers

143 views

### Induced graphs of cayley graph

I have a Cayley graph $Cay(G,S)$, its group presentation $G=< S | R >$ and it is a metric graph by assigning a length equal to 1 to each edge. I also have an induced subgraph of that Cayley ...

**1**

vote

**0**answers

61 views

### Recovering Spherical Harmonics from Discrete Samples

Consider a collection of $N$ points on the 2-sphere chosen uniformly at random. Let's say that there's an edge between two such vertices if their geodesic distance is less than $r_N$. The resulting ...

**3**

votes

**2**answers

171 views

### Definition of the Moebius Ladder Graph

I found two different definitions of the Moebius Ladder Graph, whose essential difference is, whether the smallest one shall be $K_4$ or $K_{3,3}$.
according to Wikipedia ...

**0**

votes

**0**answers

49 views

### Preferential Attachment and salton similarity in directed networks

Preferential Attachment similarity between two nodes in an undirected graph is the degree of the first node multiplied by the degree of the second node. But what about directed graphs? Which degree ...

**1**

vote

**1**answer

77 views

### Is undirected short-simple-path-through-3-vertices decidable in polynomial time?

Consider the following language:
$L=\{\langle G=(V,E),s,v,t,l\rangle\;|\;s,v,t\in V, l\in \mathbb{N} \wedge $ There exists a simple path from $s$ to $t$, going through $v$ of length $\leq l\}$.
($G$ ...

**2**

votes

**2**answers

126 views

### Which graphs generate a matroidal independence complex?

The independence complex $I(G)$ of a graph $G=(V,E)$ has as point set the vertex set $V$ and as simplices the independent sets of $G$.
Now, if $G$ is a well-covered graph (where all maximal ...

**0**

votes

**0**answers

41 views

### Almost symmetric route in digraphs

Let $D=(V,E)$ be a digraph. A route of length $k$ in $D$ is a pair $L=(S,\sigma)$, where $S=(s_1,s_2,\dots,s_{k+1})$ is a sequence of $k+1$ elements of $V$, and ...

**1**

vote

**0**answers

56 views

### Disconnecting a three regular graph

Setting, a random three regular graph. If I start removing edges, what's the probability that I disconnect it? What I know is that if I disconnect a graph I get a subgraph, and that the expected ...

**14**

votes

**1**answer

1k views

### What have simplicial complexes ever done for graph theory?

(I am asking in a somewhat tongue-in-cheek fashion, of course, but nevertheless...)
Are there examples of results in "classical" [*] graph theory that have
been achieved by using simplicial ...

**7**

votes

**0**answers

167 views

### Genus of the graph $K_{4,2,2,2}$

I have ask this question in math.stackexchange, here. Since, there is no answer and apart from that i feel that the problem is difficult, i would like to ask it here. The problem is to find the genus ...

**1**

vote

**1**answer

109 views

### The edge chromatic number and pefectness of inflation of cubic graph

The inflation of graph $G$ is a graph $I(G)$
which is obtained by replacing each vertex $x$ by a complete graph
$K_{\deg(x)}$ and joining each edge to a different vertex of $K_{\deg(x)}$.
Let $G$ ...

**5**

votes

**1**answer

190 views

### Minimum Spanning Tree of Graph with Unknown Weights

I have a fully connected graph $G=(V,E)$ with $n$ vertices. The edge weights $w(e)$ with $e\in E$ are non-negative and form a metric space (e.g. Hamming distance), thus for vertices $v,u,y \in V$, we ...

**4**

votes

**1**answer

181 views

### Do graphs with large number of paths contain large chain minor?

Definition: A "$k$-chain" is a multi-graph obtained from a path of length $k$ by duplicating every edge.
Note that the number of paths between two endpoints of a $k$-chain is $2^k.$
Question: Let ...

**4**

votes

**2**answers

171 views

### Are the following Cayley digraphs Hamiltonian?

Consider the Cayley graphs $A'G_n$ on the alternating group $A_n$ with generating set $S = \{(1i2) : 3 \leq i \leq n\}$, for $n \geq 4$.
See the following page on Alternating Group Graphs for ...

**1**

vote

**0**answers

121 views

### Knight's metric: ellipse and parabola

Knight's metric is a metric on $\mathbb{Z}^2$ as the minimum number of moves a chess knight would take to travel from $x$ to $y\in\mathbb{Z}^2$. What does a parabola (or an ellipse) became with this ...

**3**

votes

**0**answers

68 views

### Independence Number of K4-free planar graphs

The independence ratio is defined as the size of the maximum independent set divided by $n$. By the 4-color theorem, every planar graph with $n$ vertices has independence ratio at least $1/4$. ...

**0**

votes

**0**answers

39 views

### labeling graph of positive weighted vertices

is there a polynomial solution for the below problem? is it similar to a known problem in graph theory?
Given a directed graph G with cycles such that:
• G has a start node s with a path to every ...

**1**

vote

**1**answer

91 views

### Neighborhood overlap matrix for a bipartite graph

Let $G$ be an undirected, simple, bipartite graph with parts $V$ (having $n$ vertices) and $W$ (having $m$ vertices). Define the following $n$-by-$n$ matrix: for any $i,j \in V$, $$a_{ij} = |N_i \cap ...

**9**

votes

**3**answers

726 views

### Could a perfect squared square be split into two perfect squared squares?

This is a geometric puzzle though it might conceivably
also define a special class of Pythagorean triples.
A perfect squared square PSS is a square (as a plane figure)
partitioned into smaller ...

**1**

vote

**1**answer

118 views

### Max order for which connected Cayley Graphs are known to be Hamiltonian

There is a well-known conjecture that all connected Cayley graphs are Hamiltonian.
For how large a value of n has the conjecture been verified (i.e., for all groups whose order is at most n)?

**2**

votes

**1**answer

151 views

### Does index 2 subgroup imply bipartite Cayley graph?

Let $G$ be a finitely generated group and let $\Gamma=Cay(G, S)$ be the Cayley graph of $G$ with respect to some generating set $S$.
If there exists $S$ such that $\Gamma$ is bipartite, then $G$ has ...

**1**

vote

**0**answers

60 views

### interpretation of generalized eigenvalue/vectors in spectral graph theory

Let us say I have a symmetric graph adjacency matrix A, a degree matrix D, a laplacian L (D-A). I have a generalized eigenvalue equation $Av=\lambda Lv$. Does the eigenvalue/vectors produced in this ...

**6**

votes

**1**answer

143 views

### Does high min degree and high odd girth imply near bipartiteness?

Say $G$ has odd girth at least $k$ and min degree $2n/k$. There is a classical result by Andrasfai, Erdos, and Sos that says that $G$ is bipartite. (Odd girth is the length of the shortest odd cycle ...

**4**

votes

**4**answers

380 views

### Determine if a graph has a large clique

This question is quite specific and practical. I hope it is still relevant for MO and will not be removed.
I have a collection $\mathcal{C}$ of graphs having from 5000-6000 vertices and edge density ...

**5**

votes

**1**answer

158 views

### The number of connected components of a generalized hypecube

For $n$ and $m$ positive integers $n>m\ge 1$ define a graph as follows.
The vertices are the binary strings of length $n$.
Two vertices are adjacent if they differ in exactly $m$ consecutive bits. ...

**2**

votes

**1**answer

90 views

### A 3-connected graph property by Tutte

Tutte （1961): A graph $G$ is $3$-connected if and only if there exists a sequence
$G_0, ...,G_n$ of graphs that have the following two properties
1) $G_0 = K_4$ and $G_n = G$
2) $G_{i+1}$ has an ...

**3**

votes

**0**answers

37 views

### Balancing out edge multiplicites in a graph

Let $G$ be a multigraph with maximum edge multiplicity $t$ and minimum edge multiplicity $1$ (so that there is at least one 'ordinary' edge).
Is there some simple graph $H$ such that the $t$-fold ...

**7**

votes

**0**answers

106 views

### A published proof for: the number of labeled $i$-edge ($i \geq 1$) forests on $p^k$ vertices is divisible by $p^k$

Let $F(n;i)$ be the number of labeled $i$-edge forests on $n$ vertices (A138464 on the OEIS). The first few values of $F(n;i) \pmod n$ are listed below:
$$\begin{array}{r|rrrrrrrrrrr}
& i=0 ...

**5**

votes

**2**answers

206 views

### Average number of distinguished leaves in a binary tree

By a binary tree, I mean in this question a full rooted binary tree in which left and right child are labeled. A leaf of such a tree is a vertex of degree at most 1 (most references would probably ...

**3**

votes

**1**answer

626 views

### Color identical pairs and the 4-color theorem

If one could prove that for every 4-chromatic planar graph $X$ every color identical pair in $X$ is separated by a cycle, would that be a proof of the 4-color theorem?
Explanation:
A pair of ...

**2**

votes

**0**answers

57 views

### Smallest distribution of points with genuinely different clusterings

An hierarchical clustering algorithm for (finite) sets of points in a given metric space is essentially determined by its linkage criterion, which defines the distance between arbitrary (finite) sets ...

**0**

votes

**0**answers

79 views

### The largest size of a boolean subgraph (a hypercube) of a given graph

Let $G(\mathbb{F}_2^n)$ denote the graph that represents the lattice of all subspaces of $\mathbb{F}_2^n$ (also called a Hasse diagram). I am interested in knowing if there exists a large hypercube ...

**5**

votes

**2**answers

197 views

### Genus of Tutte-Coxeter Graph

What is the genus of the Tutte-Coxeter graph -- the incidence graph of the
GQ of order 2? Seems like it should be well known, since nearly every other
parameter for that graph is known, but I can ...

**4**

votes

**1**answer

97 views

### genus of a finite simple undirected graph

Let $G$ be a finite simple undirected graph. Suppose there exist subgraphs $G_1,G_2,\dots,G_n$ of $G$, such that $G_i$ and $G_j$, have no common edges and have at most two common vertices, for each ...

**3**

votes

**2**answers

148 views

### Is the domination number of a combinatorial design determined by the design parameters?

Let $D$ be a $(v,k,\lambda)$-design. By the domination number of $D$ I mean the domination number $\gamma(L(D))$ of the bipartite incidence graph of $D$.
Is $\gamma(L(D))$ determined only by ...

**5**

votes

**2**answers

89 views

### Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

A tournament is an orientation of a complete graph. A feedback arc set is a set of arcs in a digraph whose removal leave the digraph acyclic. The feedback arc set problem consists in finding a ...

**15**

votes

**1**answer

548 views

### Paul Erdős: Determine or estimate the number of maximal triangle-free graphs on n vertices

Among the collections of the open problems of Paul Erdős on the website of
Professor Fan Chung, there is one called "number of triangle-free graphs".
...

**4**

votes

**1**answer

123 views

### Nash Equilibrium in general graphical game

Any one has any ideas about how to compute the Nash Equilibrium in general graphical game? Especially, when the graph structure is not a tree.

**5**

votes

**1**answer

146 views

### The proof of Belyi theorem by Lando and Zvonkin

I'm sorry for asking such a specific question, but i have trouble understanding one detail in the proof of Belyi's theorem in the book "Graphs on surfaces and their applications" by Lando and Zvonkin" ...

**3**

votes

**1**answer

129 views

### Is the domination number NP for non-bipartite graphs?

Calculating the domination number is an NP-Hard problem. Does it remain NP-Hard if we restrict it to non-bipartite graphs?

**2**

votes

**0**answers

89 views

### Proofs about Forbidden Minors

I am working on a problem which involves proving that a particular graph is a forbidden minor of the class of graphs that i am working on.
Now i read kuratowskis theorem for planarity but i still ...

**2**

votes

**1**answer

148 views

### Coloring vertices in a cubic lattice graph and counting edges between vertices of identical and vertices of distinct coloration

Take an $A \times B \times C$ cubic lattice graph $G$, and paint $k_1$ vertices with color $c_1$ & $k_2$ vertices with color $c_2$, where $(k_1 + k_2)$ is equal to the total vertex count. Let ...

**4**

votes

**1**answer

147 views

### Which hyperbolic tilings are Cayley graphs?

I realise the question is easy but after asking to a few people (and never getting a clear answer), I thought it could be instructive to ask it here:
Given a regular tiling of the hyperbolic plane is ...

**3**

votes

**1**answer

225 views

### Flow of an integer

I've stumbled across this family of flow networks, and posted the sequence of maximal flows to OEIS. It doesn't appear at this time. I can't find any reference to it either. Has anyone seen it?
...

**8**

votes

**0**answers

203 views

### Connections between Riemann hypothesis for curves over finite fields and Ramanujan property for graphs

this question relates to the beautiful construction of expander graphs using Cayley graphs of $PGL_2(\mathbb{F}_q)$, as exposited by Davidoff-Sarnak-Valette in their book, Elementary Number Theory, ...

**13**

votes

**1**answer

630 views

### Is every graph the center of some other graph?

The center of a graph $G$ is the set of vertices that minimize the largest
distance to vertices in $G$, e.g., in the graph below, that radius is $4$:
Define the ...

**12**

votes

**3**answers

275 views

### How can I prove that a particular family of graphs is integral?

I'm working with an infinite family of graphs that seems to always have all integral eigenvalues, and I'd like to find some way to prove that (if it's true). Call the graphs $G_{n,k}$ and define them ...