Welcome to our community

Be a part of something great, join today!

Terminology on graph theory

Bingk

New member
Jan 26, 2012
16
Hello,

Just wondering if any of you have encountered a term for a particular type of graph. It is like a graph that allows for loops, but for loops, instead of joining a vertex to itself, it joins a vertex to nothing. I just want to be consistent with existing terminology, if there are none, maybe you could make some recommendations (i.e. what not to use)

The idea is this, I'm looking at properties of a simple graph, in particular, edges that are connected to vertices of the same degree. So, I don't really care about any other vertices or edges, except that in the end, I'm still talking about a simple graph.
Essentially, what I'm looking at is a set of vertices, all of which have the same degree, and edges that are incident to those vertices. So, if two of those vertices are joined by an edge, there is no problem. But, I may have edges that are incident to only one vertex (as the other end of those edges may be connected to vertices that are not yet specified).

As of now, I'm calling such graphs semigraphs. A quick search didn't show that it was being used. Someone suggested calling it a pseudograph, and in the literal sense (i.e. pseudo as a prefix), I feel it is more appropriate, but unfortunately, it seems that pseudograph is sometimes used to mean multigraphs.

Hope someone can help. Thanks!
 

Bacterius

Well-known member
MHB Math Helper
Jan 26, 2012
644
Hello,

Just wondering if any of you have encountered a term for a particular type of graph. It is like a graph that allows for loops, but for loops, instead of joining a vertex to itself, it joins a vertex to nothing. I just want to be consistent with existing terminology, if there are none, maybe you could make some recommendations (i.e. what not to use)

The idea is this, I'm looking at properties of a simple graph, in particular, edges that are connected to vertices of the same degree. So, I don't really care about any other vertices or edges, except that in the end, I'm still talking about a simple graph.
Essentially, what I'm looking at is a set of vertices, all of which have the same degree, and edges that are incident to those vertices. So, if two of those vertices are joined by an edge, there is no problem. But, I may have edges that are incident to only one vertex (as the other end of those edges may be connected to vertices that are not yet specified).

As of now, I'm calling such graphs semigraphs. A quick search didn't show that it was being used. Someone suggested calling it a pseudograph, and in the literal sense (i.e. pseudo as a prefix), I feel it is more appropriate, but unfortunately, it seems that pseudograph is sometimes used to mean multigraphs.

Hope someone can help. Thanks!
I don't think it matters that much if the name is already used, unless it is used commonly by everyone (and I've never heard the term "pseudograph" applied to multigraphs).

That said if you are looking for a unique name, how about "fractional graph", emphasising that your graph is not yet complete (integral) and is missing vertices which haven't been defined yet, hence the "floating edges". Don't know if it makes any sense but at least it's not a common appellation :confused:
 

Bingk

New member
Jan 26, 2012
16
I don't think it matters that much if the name is already used, unless it is used commonly by everyone (and I've never heard the term "pseudograph" applied to multigraphs).

That said if you are looking for a unique name, how about "fractional graph", emphasising that your graph is not yet complete (integral) and is missing vertices which haven't been defined yet, hence the "floating edges". Don't know if it makes any sense but at least it's not a common appellation :confused:
Makes sense, will consider fractional graph also. As for pseudograph being used for multigraphs, actually, I had never heard of pseudographs until this naming issue came up. It seems like because there are variations in the definition of a multigraph (i.e. allowing for loops or not), pseudograph is being promoted as the word to use when you allow for both loops and multiple edges.

Thinking along the lines of hypergraphs, I came up with 2 more possibilities, "1,2-uniform hypergraph" or "hypograph".
 

Ackbach

Indicium Physicus
Staff member
Jan 26, 2012
4,193
Or you could call it a "half-graph". Then your name rhymes with itself. ;)
 

Bingk

New member
Jan 26, 2012
16
Thanks!

I'll give it a few more days, but from what I've read so far, it seems like there's no official name for the type of graph I'm concerned with...maybe we can put up a vote for it, hehehe.