-4
$\begingroup$

If given a simple, integer-labeled, but not necessarily connected, graph $G := (V,E)$ consisting of at least one vertex, i.e. $\lvert \rvert V \lvert \rvert \geq 1$, then is there a function to unambiguously assign it a positive integer value like a serial number? What is the simplest (least computationally complex) mapping or function $f:G\mapsto \mathbb N$ from all possible simple $G$ to the set of natural numbers $\mathbb N$ such that every $\gamma=f(G)$ is a distinct element of the natural humbers $f(G)\in\mathbb N$ for all $G$?

Hint: $f(G)$ need not be surjective with regard to the codomain of positive integers just its image which you could call $\mathbb \Gamma$.

$\endgroup$
13
  • 1
    $\begingroup$ The constant 0 function. $\endgroup$ Feb 25 '19 at 8:12
  • 2
    $\begingroup$ I think the 'unambiguously' makes this question go from easy to impossible. Assigning each graph a number so that you can recover the graph from the number is easy. Requiring the number to be unique means you have to solve all the graph isomorphism problem. Given two graphs deciding whether they are isomorphic or not is a hard problem in general. $\endgroup$
    – quarague
    Feb 25 '19 at 9:22
  • 8
    $\begingroup$ Write the upper triangle of the adjacency matrix out as a string of $\binom n2$ bits and call it a binary number. If all labelled graphs are possible, this is optimal in speed and space. $\endgroup$ Feb 25 '19 at 12:39
  • 2
    $\begingroup$ @StuartLaForge Brendan McKay's method can be modified by appending a 1 at the beginning of the binary strings, which would resolve your problem. $\endgroup$ Feb 25 '19 at 15:25
  • 2
    $\begingroup$ What is the "fa.functional-analysis" aspect of the question? I suggest to remove it as misleading. $\endgroup$
    – TaQ
    Feb 25 '19 at 17:22
0
$\begingroup$

I apologize in advance for my abuse of set notation as I am mapping one mathematical object that is not quite a set i.e. graphs to another mathematical object that is not quite a set i.e. sequences. Feel free to comment or correct notation etc.

Definitions:

(1) The triangular-harmonic numbers $\Theta$ are a monotonic sequence of rational numbers greater than or equal to one defined recursively as follows:

$$\Theta := \bigcup_{\forall k}\{\theta_k \in\mathbb Q\mid \theta_k \geq 1\}\\ \theta_0 = 1\\ \theta_k = \theta_{k-1}+\frac{1}{\lfloor \theta_{k-1}\rfloor} $$ The first few terms of $\Theta$ are: $$\left\{1,2,2+\frac{1}{2},3,3+\frac{1}{3},3+\frac{2}{3},...\theta_k\right\}$$

I am grateful to Carlo Beenakker for helping me find the closed form of $\Theta$ which is $\theta_k=\frac{T_k^{-1}}{2}+\frac{k}{T_k^{-1}}+\frac{1}{2}$ for $k\geq 1$ where $T_k^{-1}=\left\lfloor\sqrt{2n}+\frac{1}{2}\right\rfloor$ is the inverse triangular number function. https://oeis.org/A002024

(2) The index function of $\theta_k$ is found by solving the closed form for $k$: $$k(\theta_k)=\frac{2\lfloor \theta_k \rfloor \theta_k- \lfloor \theta_k \rfloor^2- \lfloor \theta_k \rfloor}{2}$$

(3) The edge-value function $\mathcal E$ is a function that maps the edges of a natural number-labelled graph to the rational numbers as follows:

\begin{equation} \text{if }\ G=(V,E) \text{ with }\ V=\{1,2,3 ...n\}\Longrightarrow\exists \mathcal E:E\mapsto \mathbb Q\\ \mathcal E(e_{ij})=\frac{j^2+i}{j}=j+\frac{i}{j}\\ \text{ where }\ i<j \text{ and }\ i,j \in V \end{equation}

Theorem: The rationally-ordered graph theorem.

Claim: If the vertices of a simple graph are uniquely labeled with integers, then the whole graph can be uniquely mapped to a monotonic sequence of rational numbers that is a subset of $\Theta$ the triangular-harmonic numbers.

If $V(G)=\{1,2,3 ..., n\} \Rightarrow \exists \text{ sequence } S_k$ of monotonically increasing rational numbers where $S_k<S_{k+1}$ for all $k$ and $ \{S_k\}_{\forall k} \subset \Theta$.

Proof:
Consider building a sequence of complete graphs over n vertices, one vertex at a time, starting with the one-vertex complete graph $K_1$ labeled with the integer 1. $$\text{Let }\ K_1 = (V,E) = (\{1\},\{\})\\$$ Adding a second vertex and applying the previously defined edge-ordering function $\mathcal E(e_{ij})\mid e_{ij}\in E(K_n)$ over all edges in $K_2$ gives us:

$$K_2 \longmapsto V(K_2) \bigcup_{\forall e_{ij} \in E(K_2)} \mathcal E(e_{ij})=\left\{1,2,2+\frac{1}{2}\right\}$$

$$K_3 \longmapsto V(K_3) \bigcup_{\forall e_{ij} \in E(K_3)} \mathcal E(e_{ij})=\left\{1,2,2+\frac{1}{2},3,3+\frac{1}{3},3+\frac{2}{3}\right\}$$ $$\cdot$$ $$\cdot$$ $$\cdot$$ $$K_n \longmapsto V(K_n) \bigcup_{\forall e_{ij} \in E(K_n)} \mathcal E(e_{ij})=\left\{1,2,2+\frac{1}{2},3,3+\frac{1}{3},3+\frac{2}{3}, … ,n,n+\frac{1}{n}, ..., n+\frac{(n-1)}{n}\right\}$$

Simple inspection shows that $K_n \longmapsto S= \{\theta_k\}_{k=0}^{T_n-1}$ where $T_n$ denotes the $n^{th}$ triangular number i.e. $T_n=\frac{n^2+n}{2}$.

Now consider that all simple graphs of order n are spanning subgraphs of the complete graph of order n and it becomes clear that the rational sequence of any finite simple graph is a finite subsequence of the trianguar-harmonic numbers:

$$\text{If } G_n \in \{\text{simple graphs}\}\text{ and }G_n \subset K_n \Longrightarrow G_n \mapsto S \mid S \subset \Theta\\ \blacksquare$$

Corollary 1: Index of simple graphs There exists an index on all simple graphs of order $n$ such that the computational complexity of each of the indices is on the order of $ O(n^2)$ bits.

Proof: Given a simple graph $G=(V,E)$ of order $n$, one uses the rationally ordered graph theorem to derive a "graph sequence" $S$ of rational numbers such that the integers denote vertices $V = \{v_1,v_2,v_3,...,v_n \mid v_n \in \mathbb N \}$ while improper fractions denote the edges between them $E=\left\{\frac{v_j^2+v_i}{v_j}\mid v_i < v_j \text{ for }\forall (v_i,v_j) \in E\right\}\text{ }\therefore S(G\mapsto\Theta)=V \cup E$.

Since from the ROG theorem we know that $S \subset \Theta$ we can simply find the index number of graph $G$ by calculating the sum: $$I(G)=\sum_{\forall i \in S} 2^{k(i)}$$

Therefore for a graph $G_n$ of order $n$ between the limits of an empty graph and a complete graph we have: $$\sum_{i=1}^{n}2^{T_n-1} \leq I(G_n) \leq 2^{T_n}-1$$

Since $\lim_{n\to\infty}T_n=\lim_{n\to\infty}\frac{n^2+n}{2}=\lim_{n\to\infty}n^2=\infty\Longrightarrow O(n^2)$ $$\blacksquare$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.