# Tagged Questions

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$. ...
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 ...
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)?
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 ...
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 ...
36 views

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 ...
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 ...
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 ...
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?
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
### 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!