5
votes
0answers
29 views

Name for Number of Ancestors/Descendants of Vertex in Directed Acyclic Graph

Let $G = (V, E)$ be a directed acyclic graph. For each vertex $v \in V$, define the ancestors of $v$ to be the set of vertices $u \in V$ such that there exists a directed path from $u$ to $v$. ...
0
votes
0answers
20 views

What is the edge called that converts a tree to a directed acyclic graph?

Neither Wikipedia nor mathworld gave the answer: What is the name of the edge (or multiple edges) without which a DAG would be a tree? Or maybe instead: What is the name of the subgraph such that ...
2
votes
1answer
49 views

How to call a tree with a single branch?

How do you call a tree with only one branch (in other words, where every vertex has maximum one direct successor)?
5
votes
1answer
87 views

What is the name of a graph made of k copies of a 4-cycle connected end to end in a chain, possibly with leaves?

Do graphs of the following sort have a specific name? We've been calling them Cactapillars, as they're cacti that look a little like caterpillars (and the name Caterpillar already refers to a ...
1
vote
1answer
23 views

Name for a generalized relation to be a multiset?

A relation between two sets $A$ and $B$ is a subset of $A \times B$. If taking a multiset subset of $A \times B$, e.g. allowing $(a,b)$ appears twice in the subset, is there a name for such a ...
0
votes
0answers
36 views

A graph with single circle

Is there a name for a (directed) graph that has exactly one circuit that goes through all of its vertices (in the same direction)? If so, what is it called? Example is as follows: $$A\to B, B \to C, ...
1
vote
1answer
29 views

Corresponding graph: Forest <-> Tree, “???” <-> Polytree

Is there a specific term for a graph, that consists of Polytrees, like a Forest consists of Trees? Or can a Polytree be disconnected?
2
votes
1answer
42 views

How many contiguous subsets of size $N$ does an infinite grid have?

Suppose I have an infinite grid. How many sets of grid points are there that contain $N$ contiguous grid points, and include the grid point at the origin? So for example, if $N$ = 2, then there are 4 ...
0
votes
0answers
18 views

Number of orientations of a graph without a source

An orientation of an (undirected, loopless) graph is an assignment of direction to each edge, turning the graph to a directed graph. A source in a directed graph is a vertex with outdegree equal to ...
1
vote
0answers
129 views

“Dual cardinality” in the graphs $(V_\alpha,\in_\alpha)$

04-25-2014 Enriched with more details Let define the graphs $(V_\alpha,\in_\alpha)$ in $ZFC$ $V_\alpha$ can be finite too $\in_\alpha \subseteq V_\alpha \times V_\alpha$ and ...
0
votes
1answer
39 views

What's maximal clique?

I'm unable to understand what maximal clique is. I mean how a clique can't be extended by a node and remain a clique? If I add a node and then I connect this node to every other nodes in the clique, ...
0
votes
0answers
24 views

mean number of links in adjacency matrix

I have converted from an individual-level adjacency matrix to one for clusters and I am trying to show mathematically how I programmed up determining the mean number of inter-cluster links. I am not ...
2
votes
1answer
27 views

Is there a name for a directed graph in which every vertex has outdegree one?

Per the question title, I'm dealing with a number of directed graphs, all of which are 1-out regular, and figure that there is probably a name for such a thing. Unfortunately, all my search attempts ...
0
votes
0answers
28 views

An interleaved path of arrows in a category/digraph

In what I am doing now, a slightly strange concept emerged; My objects are sequences of arrows $\{f_i\}_{i=1}^{n}$ in a small category such that for every $1\leq i\leq n-1$, there is an arrow from the ...
3
votes
1answer
40 views

Odd and Even Triangles

I am about to make a report on the topic of characterization of line graphs then I came across the terms "odd triangles" and "even triangles". Does anyone know what these terms mean? To elaborate, I ...
1
vote
1answer
58 views

Graph nomenclature

This concerns graphs that are sets of vertices and edges G={V,E}, not graphical depiction of functions. Imagine a graph that is a 2D square mesh of vertices. Such a graph can be constructed, for ...
2
votes
1answer
51 views

Hypergraph terminology

Suppose I have a hypergraph with vertices V and hyperedges H, where each hyperedge is a subset of V. I want to form a normal graph with vertex set V, where two vertices are adjacent if they lie in ...
2
votes
1answer
133 views

Is there a name for this property of a binary relation? $\forall x\forall y(x\mathsf{R}y\to\exists z(x\mathsf{R}z\land y\mathsf{R}z)))$

Consider a binary relation $\mathsf{R}$ such that $x\mathsf{R}y$ is the case only if there is some $z$ such that both $x\mathsf{R}z$ and $y\mathsf{R}z$ are the case. Is there a well-known name for the ...
3
votes
1answer
31 views

Families of graphs where the shortest path between vertices uniquely determines vertex pairs

Imagine a graph $G$ with unlabeled vertices and unlabeled edges, and where we have an arbitrary vertex pair $(v_1,v_2)$. Let $k$ be the length of the shortest edge-wise path between $v_1$ and $v_2$. ...
2
votes
2answers
43 views

Comparison of almost planar graphs

I have multiple graphs all of which are almost planar. Is there any existing terminology / method which compares them, such that one can say which one is more planar? This could simply be the required ...
0
votes
0answers
15 views

Correct terminology for a non minimal directed graph containing a closed walk?

Please bare with me, mathematics is not my first language I am searching for the correct terminology for a directed graph that includes both a loop and some open edges? I have been reading the ...
0
votes
2answers
78 views

Does this graph have a special name? (8-connected neighborhood)

Does this graph have a special name? The vertices are arranged on a square square grid with a side length of $n$ and each inner vertices has an edge to its 8 neighbors. And what about a similar ...
0
votes
1answer
25 views

Formal name for a closed connected graph

I have to name an abstraction representing a mechanical truss diagram. It consists of a set of polygons that must overlap, viz. share an edge or a corner. In other words it must not only be a ...
3
votes
2answers
86 views

Terms of graph theory in english

Can anyone please tell me how are these graphs called in english? If we can divide a set of graph vertices in two disjoint sub sets, such as all edges connect vertices only inside these sub sets? ...
2
votes
3answers
2k views

In graph theory, what is the difference between a “trail” and a “path”?

I'm reading Combinatorics and Graph Theory, 2nd Ed., and am beginning to think the terms used in the book might be outdated. Check out the following passage: If the vertices in a walk are ...
1
vote
0answers
20 views

Terminology for a graph that can be drawn in several planes?

A graph is called planar if you can draw it in the plane without any edges crossing. In circuit layouts, it's common to try to lay out a graph across multiple different planes, where edges can jump ...
0
votes
1answer
60 views

What is a cycle hypergraph?

What is a cycle hypergraph? Could someone give me good reference or illustrate with a few examples?
1
vote
0answers
68 views

Graph theory name for minimum depth to leaf node.

In a graph theory rooted tree, is there a name for the minimum depth downwards to reach a leaf node? I have in mind calculating "depth to a leaf" at each node by looking downwards through the subtree ...
2
votes
2answers
120 views

The use of any as opposed to every.

This is a really basic question, but it is one I never really thought about until now. Let $\mathscr{G}$ be a tree. Then every pair of vertices in $\mathscr{G}$ is connected by a unique walk. We ...
1
vote
2answers
48 views

Graphs with pairs of vertices connected by multiple edges

Is there a common name for this kind of graphs (directed or not)? Thank you.
0
votes
0answers
117 views

Symbol for the incidence relation between vertices and edges.

Q: Suppose $G$ is a graph whose vertices are $V$ and edges are $E$. Is there a standard symbol for the relation $R$ on $V\times E$ such that $vRe \iff $ v is a vertex of $e$? ...
2
votes
0answers
83 views

What type of graph is this. I shows kind of cause and effect.

I am trying to create a chart like this that shows item 1 effects items 2 and 4 type chart. I didn't really know where to post this so I thought mathematics would be the right place because of the ...
4
votes
1answer
99 views

Nomenclature and notation for some aspects of weighted directed graph.

I'm having some problem with nomenclature some structures and quantities related to weighted directed graph. Suppose that $A \in \mathbb{R}_+^{N \times N}$ is the weighted adjacency matrix of a ...
2
votes
1answer
66 views

What is “group of graph”?

I'm reading some old article and I have one small question: what in general is the group of a graph? By the article, definition should be in Harary's Graph Theory, but unfortunately I don't have any ...
0
votes
0answers
48 views

What is that type of TSP

I'm searching for the name of the TSP-like problem. The basic principal is like it follows: When a city is visited by the salesman, he will came in one point and exit the city in another. The ...
7
votes
2answers
156 views

Is there a name for relations with this property?

Is there a name for relations $\rho : X \rightarrow Y$ such that for all $x,x' \in X$ and all $y,y' \in Y$ we have that the following conditions $$xy \in \rho$$ $$x'y \in \rho$$ $$xy' \in \rho$$ imply ...
1
vote
1answer
81 views

authority distribution and hub distribution

I want to understand the concepts authority distribution and hub distribution. As I see in gephi software, Authority measures how valuable information stored at that node is. Hub measure the quality ...
2
votes
2answers
501 views

difference between “minimal” and “minimum” edge cuts.

I was going through the topic about connectivity of graphs. There it was mentioned about the terms "minimum edge cut" and "minimal edge cut". I know both are the sets of edges if removed from the ...
3
votes
1answer
33 views

Names and algorithms for subgraphs with smallest neighbourhoods

I'm curious about some terminology for graphs and the existence of an algorithm. Let $G$ be a graph and $H \leq G$ a subgraph. Is there a name given to $H$ if $|N(H)|$ is minimum over all subgraphs ...
0
votes
2answers
397 views

Is a loop actually a circuit?

If I have a single vertex with a self-loop. Do we call that a circuit? Because we "loop" around itself once?
0
votes
0answers
60 views

How does directional graph without loops but with many paths called?

If each node has many childs but only one parent then graph is called "tree". But what if there are many of parents too? The structure will also contain no loops and will look like some paper ...
0
votes
1answer
39 views

What to call a vertex that lies on every maximum matching?

Is there a commonly used name in the literature for vertices in a graph that lie on every maximum matching? I have seen these vertices appear in several induction proofs, mostly in graph ...
3
votes
1answer
59 views

What is the name of graph problem that ask to select some vertices to see every edges.

I want to place light bulbs on some vertices (each bulb will lit up every edges it connected) where all edges lit up. e.g. suppose I have this simple planar graph, Sufficient vertices to place ...
2
votes
2answers
137 views

What is a Ramsey Graph?

What is a ramsey graph and What is its relation to RamseyTheorem? In Ramsey Theorem: for a pairs of parameters (r,b) there exists an n such that for every (edge-)coloring of the complete graph on n ...
1
vote
3answers
108 views

What is the term for a graph on $n$ vertices with no edges?

What is the term for a graph comprised of $n$ pairwise disconnected vertices? I could call these $1$-colorable graphs or something like that, but I would rather use standard terminology if it ...
0
votes
1answer
482 views

What does one mean by NOT directed acyclic? Doesn't it means the same as directed acyclic?

I did this question in a course and it is Consider our algorithm for computing a topological ordering that is based on depth-first search (i.e., NOT the "straightforward solution"). Suppose we run ...
2
votes
2answers
162 views

What graph is this?

For my game I am trying to implement a continues world by interconnecting the nodes like below I beg your pardon for my bad drawings I don't know how to explain it but its NOT DENSE GRAPH It is ...
4
votes
0answers
339 views

What is a bridgeless undirected planar 3-regular bipartite graph?

Draks asked a question about a sentence in Wikipedia stating that such-and-such (NP-hardness of Hamiltonian path detection) is true for "bridgeless undirected planar 3-regular bipartite graphs". What ...
3
votes
1answer
85 views

Does anyone know the name of the following problem?

At a given day a number of $N$ salesmen (from the same company) are randomly scattered in a landscape with $M$ cities. At the next day as many cities as possible should have a salesman visiting, no ...
2
votes
2answers
78 views

Does a graph with $0$ vertices count as simple?

Does a graph with $0$ vertices count as a simple graph? Or does a simple graph need to have a non-empty vertex set? Thanks!