show/hide this revision's text 2 added 134 characters in body

Every simple graph $G$ can be represented ("drawn") by numbers in the following way:

  1. Assign to each vertex $v_i$ a number $n_i$ such that all $n_i$, $n_j$ are coprime whenever $i\neq j$. Let $V$ be the set of numbers thus assigned.

  2. Assign to each maximal clique $C_j$ a unique prime number $p_j$ which is coprime to every number in $V$.

  3. Assign to each vertex $v_i$ the product $N_i$ of its number $n_i$ and the prime numbers $p_k$ of the maximal cliques it belongs to.

Then $v_i$, $v_j$ are adjacent iff $N_i$ and $N_j$ are not coprime,

i.e. there is a (maximal) clique they both belong to. Edit: It's enough to assign $n_i = 1$ when $v_i$ is not isolated and does not share all of its cliques with another vertex.

Being free in assigning the numbers $n_i$ and $p_j$ lets arise a lot of possibilites, but also the following question:

QUESTION

Can the numbers be assigned systematically such that the greatest $N_i$ is minimal (among all that do the job) — and if so: how?

It is obvious that the $n_i$ in the first step have to be primes for the greatest $N_i$ to be minimal. I have taken the more general approach for other - partly answered - questions like "Can the numbers be assigned such that the set $\lbrace N_i \rbrace_{i=1,..,n}$ fulfills such-and-such conditions?"

show/hide this revision's text 1

Drawing (graphs) by numbers: a minimality question

Every simple graph $G$ can be represented ("drawn") by numbers in the following way:

  1. Assign to each vertex $v_i$ a number $n_i$ such that all $n_i$, $n_j$ are coprime whenever $i\neq j$. Let $V$ be the set of numbers thus assigned.

  2. Assign to each maximal clique $C_j$ a unique prime number $p_j$ which is coprime to every number in $V$.

  3. Assign to each vertex $v_i$ the product $N_i$ of its number $n_i$ and the prime numbers $p_k$ of the maximal cliques it belongs to.

Then $v_i$, $v_j$ are adjacent iff $N_i$ and $N_j$ are not coprime,

i.e. there is a (maximal) clique they both belong to.

Being free in assigning the numbers $n_i$ and $p_j$ lets arise a lot of possibilites, but also the following question:

QUESTION

Can the numbers be assigned systematically such that the greatest $N_i$ is minimal (among all that do the job) — and if so: how?

It is obvious that the $n_i$ in the first step have to be primes for the greatest $N_i$ to be minimal. I have taken the more general approach for other - partly answered - questions like "Can the numbers be assigned such that the set $\lbrace N_i \rbrace_{i=1,..,n}$ fulfills such-and-such conditions?"