Is there a name for this type of graphs?

72 Views Asked by At

From a graph G I want to construct a graph (lets call it) G# with the following properties:

  • Each node and each edge of G is a node of G#
  • For each e in G connecting the nodes n1, n2 there exist the edges connecting e,n1 and e,n2
  • no other edges exist in G#

G# is then bipartite with the nodes and edges of G being it's disjoint sets´. It's like creating the line graph of G and stopping after the creation of the "new nodes".

Is there a name for this special kind of graph?

2

There are 2 best solutions below

2
On BEST ANSWER

It is called the (first) barycentric subdivision of the graph.

0
On

This is more like the Total Graph than the Line Graph (because the nodes of $G\#$ consist of both the nodes and the edges of $G$), except that adjacency in $G\#$ is determined only by incidence in $G$, rather than both incidence and adjacency in $G$ (which is the case in Line Graphs).

This is called the Incidence Graph in configurations, though it doesn't seem to be popular in graph theory itself. As you correctly said, it is a bipartite graph.