**-3**

votes

**0**answers

25 views

### Calculate minimal number of nodes? [on hold]

Calculate minimal number of nodes? in a loopless simple undirected pi-partite graph. that has exacatly 144 nodes

**-3**

votes

**0**answers

27 views

### Directed and undriected trees [on hold]

How many different directed trees can be obtained if we assign all possible orientation to the edges of an undirected tree having exactly 7 nodes? how many of them will be rooted(directed) trees?

**0**

votes

**0**answers

33 views

### Determine number of directed trees and rooted trees obtainable [on hold]

I've been doing some exercices about graph theory and I find myself stuck on this one with no idea of to proceed.
Here's the question :
how many different directed trees can be obtained if we assign ...

**-2**

votes

**0**answers

45 views

### Is there such a thing as cyclic Hasse diagram for posets? [on hold]

If so can you name one ? If not how to prove that there is none? Thanks !

**2**

votes

**0**answers

46 views

### Maximal $k$-chordal subgraph

Recall that a graph is called $k$-chordal if any cycle $C$ of length $> k$ contains a chord, i.e. an edge joining to non-consecutive vertices in $C$. Let $f(n, k)$ be the minimal number of edges ...

**1**

vote

**1**answer

66 views

### How to calculate the maximum number of rainbows for arbitrary graphs?

This question is inspired by problem 1 of the combinatorics test of the 2012 third round iranian olympiad which is as follows:
We've colored edges of $K_n$ with $n-1$ colors. We call a vertex rainbow ...

**2**

votes

**1**answer

79 views

### Distance between two networks

Suppose you have networks A and B, each with a set of nodes and edges. You want to measure how similar the networks are to each-other. None of the nodes or edges are labelled. What are the metric(s) ...

**2**

votes

**0**answers

59 views

### Reconstructing a function from its variants that negate one argument

Call two functions $g(x_1,\ldots,x_n)$ and $h(x_1,\ldots,x_n)$ from complex numbers to complex numbers equivalent if they are the same up to the order of their arguments. Formally: there is a ...

**5**

votes

**1**answer

125 views

### Integral straight-line embeddings of planar graphs

Wikipedia says (in the article on Fáry's theorem),
"Heiko Harborth raised the question of whether every planar graph has a straight line representation in which all edge lengths are integers. The ...

**4**

votes

**1**answer

86 views

### Extremal graph theory for directed graphs

In extremal graph theory, there are results such as
$$t(C_4,G)\geq t(K_2,G)^4,$$
where $G$ is an undirected graph, $C_4$ is a cycle graph on 4 nodes, $K_2$ is a complete graph of $2$ nodes, and ...

**-1**

votes

**0**answers

29 views

### departure time/overlap algorithm [closed]

i'm looking for "departure time/overlap algorithm" or any other idea.
Suppose you have n trains and each one has a performance profile(how much electricity they need at the current time while driving ...

**2**

votes

**1**answer

60 views

### Eigenvalues of a graph and its one-edge-delation graph

Let $G$ be any graph with at least one edge and let $e$ be any edge of $G$. Let $G-e$ denote the subgraph of $G$ obtained by deletion of the edge $e$. Assume that $G$ has $n$ vertices.
Suppose ...

**3**

votes

**1**answer

80 views

### A problem related to routing in a graph

I have come across a new problem - I want to know whether this problem is similar to some existing problem or not.
The new problem is this. There is a tourist who has a having the following ...

**0**

votes

**1**answer

101 views

### Spectral Graph Theory

Let G be an undirected graph, then
Laplacian Matrix(L(G)) = Degree Matrix (D(G)) - Adjacency Matrix (A(G)).
What is the relationship between laplacian and adjacency spectrum of undirected graphs?

**0**

votes

**1**answer

62 views

### Laplacian matrix of a graph with negative weights

I am trying to calculate the Laplacian and Adjacency matrix of a graphs for positive and negative weights. If a graph be simple with only non-negative weight it is easier. But in my graph I have some ...

**7**

votes

**4**answers

287 views

### Extremal examples for a folklore lemma on subgraphs of large minimum degree

It's a well known fact that a graph $G$ of average degree $d$ has a subgraph $G'$ of minimum degree at least $d/2$ and that the constant $1/2$ cannot be improved. The proof I know, which proceeds by ...

**3**

votes

**0**answers

118 views

### Must distinct tree eigenvalues be relatively far apart?

How close to each other can two distinct eigenvalues of a tree be, as a function of the number $n$ of nodes ?
For example, the path $P_n$ exhibits a gap of order $\frac{2\pi^2}{n^2}$ asymptotically ...

**1**

vote

**0**answers

29 views

### Euclidean embedding of a graph based on 1-ring neighborhood distances only

Consider a graph $(V,E)$, $\vert V \vert = n$ and weights $\{l_{ij}\}$, where $l_{ij}>0$ iff there is an edge connecting vertices $v_i$ and $v_j$. Distances beyond the 1-ring neighborhood are not ...

**4**

votes

**1**answer

114 views

### Graph presentation of Lexicographic shifts

Consider a finite alphabet $\{0,1, \ldots, n-1\}$. Let $\Sigma_n = \mathop{\prod}\limits_{j=1}^{\infty}\{0, \ldots n-1\}$ be the set of infinite one sided sequences and $\prec$ the lexicographic ...

**1**

vote

**1**answer

128 views

### Degree Sequence Problem on $k$-Partite Graphs

The general Degree Sequence Problem asks for a simple undirected graph (that is a graph without self-loops and with no more than one edge between any pair of nodes) for which it holds that the degrees ...

**0**

votes

**0**answers

23 views

### “Mutant knots” generalizable to “mutant tangled graphs”?

Just in case: Take a link L (drawn into the plane with over- and undercrossings),
draw a closed loop C on it which cuts L in four points, rotate the inside of C
around 180° (align the cut points on ...

**5**

votes

**0**answers

72 views

### Implementations of Tutte polynomial [reference request, of a kind]

This question is not a 100% fit for MO, but it is a serious question that can be viewed as a sort of reference request, and I think fits here more than elsewhere.
I have been asked to write a chapter ...

**2**

votes

**1**answer

224 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

45 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

54 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

133 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

57 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

121 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

40 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

65 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

114 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

40 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

156 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

100 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

168 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

168 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

168 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

103 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

49 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

36 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

74 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

698 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

116 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

142 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

49 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

142 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

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

**1**

vote

**0**answers

82 views

### Motivations Needed: Paul Erdős Maximal Triangle-free Graphs

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