1
$\begingroup$

Consider a simple binary undirected graph, which adjacency matrix is $A = \{a_{i,j}\} \in \{0, 1\}^{N \times N}.$

Suppose that all vertices of such graph have at least one neighbors, i.e.

$$k_i = \sum_{j=1}^N{a_{i,j}} \geq 1.$$

How do we call this graph?

Reading the definition of connectivity, I did not find anything about this particular case.

I would say that it is "minimally connected".

Is there a proper nomenclature for these graphs?

$\endgroup$
2
  • $\begingroup$ What is a "binary" graph? $\endgroup$
    – richarddedekind
    Dec 8, 2018 at 3:41
  • 1
    $\begingroup$ Binary stands for "non-weighted", i.e. the entries of $A$ are in the set $\{0, 1\}$, not in $\mathbb{R}^+$. $\endgroup$
    – the_candyman
    Dec 8, 2018 at 11:42

1 Answer 1

Reset to default
4
$\begingroup$

Requiring that every vertex have positive degree is not sufficient to make the graph connected. You may describe your graph as having no isolated vertices.

$\endgroup$
1
  • $\begingroup$ this makes sense. thanks a lot. $\endgroup$
    – the_candyman
    Dec 8, 2018 at 11:42

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .