Just going through some graph theory concepts and I have two elementary questions which must be pretty trivial (but sometimes what seems trivial to me turns out to be wrong, so I'd be happy if someone could confirm that the following are indeed true):

(1) A periodic graph cannot self-loops - because self-loops are cycles of length 1.

Each graph $G$ can be split into strongly connected components and the 'rest of the world' $R$ (nodes in no connected component but with possible links to connected components).

(2) If $G$ is undirected, $R$ can only consist of isolated nodes (nodes with links to no other node).

  • $\begingroup$ Could you expand on $(1)$? I'm not sure what it's asking. $\endgroup$ – none Dec 7 '15 at 4:49
  • $\begingroup$ en.wikipedia.org/wiki/Aperiodic_graph $\endgroup$ – DrWatson Dec 7 '15 at 8:05
  • $\begingroup$ Ah, the question looks like "A periodic graph" rather than "Aperiodic graph". For $1$ it seems that an aperiodic graph can have self-loops, since the definition asks for an integer $>1$ that divides the cycle lengths. For $2$, assume $R$ contains a non-isolated vertex. Then, that vertex forms a connected component of size $ \geq 2$ in an undirected graph. $\endgroup$ – none Dec 7 '15 at 8:14
  • $\begingroup$ @SanicHodgeheg A periodic graph is one that is not aperiodic, dude. Standard concept in graph theory. $\endgroup$ – mathse Dec 7 '15 at 8:30
  • $\begingroup$ Your "disproof" of 2 seems to be wrong, too. You make a connected component out of $R$, but then $R$ does not satisfy its definition, which is: not to be a connected component. $\endgroup$ – mathse Dec 7 '15 at 8:37

Your Answer

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

Browse other questions tagged or ask your own question.