Tagged Questions

13 views

Tree of arity n: How to call a vertex that has only k (k<n) children?

What is the correct adjective for a vertex in an n-ary tree that has only k children (k < n)? I was thinking of something like "unsaturated", but I don't know if that is the correct word for this. ...
31 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$. ...
21 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 ...
51 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)?
89 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 ...
25 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 ...
36 views

84 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 ...
547 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 ...
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 ...
423 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?
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 ...
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 ...
60 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 ...
141 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 ...
109 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 ...
485 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 ...
163 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 ...
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 ...