2
$\begingroup$

Consider an undirected graph. It's obvious what is a vertex (≙ object) and what is an edge (≙ fact).

    alt text (source)

Now "objectify" the edges (≙ facts) by adding an extra vertex along every edge.

    alt text (source)

In general, in the "(edge-)objectified" graph it's not determined anymore which vertices correspond to "objects" and which vertices correspond to "facts", e.g. in objectified cycle graphs. But sometimes it is, e.g. in objectified path or star graphs.

In the case of cycle graphs, the objectified graph can nevertheless be "un-objectified" uniquely.

How can graphs be characterized

  1. for which "objects" and "facts" can be distinguished in their "objectified" graph (like in path and star graphs)

  2. that can be "un-objectified" uniquely (like cycle graphs)

Where can I learn more about this approach? Under which term is it filed?

Improve this question
$\endgroup$
2
  • $\begingroup$ If you square the new graph with edge subdivisions, you get a disjoint union of your original graph and its line graph. So another way of phrasing the answer below is that the only graphs which are line graphs of their graphs are unions of cycles. $\endgroup$
    – Gjergji Zaimi
    Commented Apr 22, 2011 at 10:00
  • $\begingroup$ Lexicographic note: the usual term for the above kind 'objectify' is subdivide. (This is already mentioned in Tony Huynh's answer, but should be more conspicuous in this thread.) Also, this graph-theoretic kind of 'subdivide' is an instance of the concept of barycentric subdivision in topology. Philosophical note: assuming 'naive realism', the reconstruction-issue is moot: then 'objects' are of different sort than the 'facts' (which I imagine as texts); on the other hand, assuming 'everything is language', there's a point to the above: then, each fact is of the same sort as the objects. $\endgroup$
    – Peter Heinig
    Commented Dec 11, 2017 at 8:12

1 Answer 1

Reset to default
5
$\begingroup$

If I understand your questions correctly, I think the answer to (1) is all graphs not containing a cycle as a component, and the answer to (2) is all graphs.

Let $G'$ be the graph obtained from a connected graph $G$ by subdividing each edge once. Note that $G'$ is bipartite and has a bipartition $(A,B)$ where each vertex in $A$ has degree 2. If $B$ has a vertex of degree not equal to 2, then the vertices in $B$ correspond to the vertices of $G$, and so we can recover $G$ from $G'$. Otherwise, $|A|=|B|$ and $G'$ is a cycle. In the second case we can still recover $G$ from $G'$, but cannot distinguish objects and facts.

Improve this answer
$\endgroup$
3
  • $\begingroup$ more precisely (1) all graphs not containing a $2$-regular component (a cycle) $\endgroup$
    – Flo Pfender
    Commented Apr 22, 2011 at 3:14
  • $\begingroup$ Doesn't "graphs not containing a cycle" mean "forests"? $\endgroup$
    – Hans-Peter Stricker
    Commented Apr 22, 2011 at 9:57
  • $\begingroup$ There could be some non-associativity of language coming into play here, but I just mean all graphs that do not contain a connected component which is a cycle. $\endgroup$
    – Tony Huynh
    Commented Apr 22, 2011 at 10:24

You must log in to answer this question.

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