Tagged Questions
0
votes
0answers
40 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
1answer
82 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
17 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
50 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
23 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
54 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
47 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
31 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
33 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
73 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
76 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
58 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
127 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 ...
2
votes
0answers
64 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 ...
0
votes
0answers
34 views
Name of the inverse of a reduced node-arc incidence matrix
So I basically have a directed incidence matrix 'A' and its inverse 's' has been labelled as "sensitivity matrix"; is that right? {the label is a comment in a matlab program}
Also, it's been said ...
3
votes
1answer
78 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
75 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!
2
votes
1answer
83 views
Nomenclature of matrices used in graph theory
So far I've come across a bunch of different terms for matrices used in graph theory - adjacency matrix, connectivity/connection matrix, vertex matrix, etc.
Are there any differences between these ...
0
votes
0answers
46 views
Abbreviations in Combinatorial Graph/Matrix theory
I'm getting started with research in combinatorics. I have come across a reference that uses a great deal of abbreviations. I was able to figure most of them out but there are a few that I can find.
...
2
votes
2answers
30 views
What are the sets of vertices in a proper vertex coloring referred to?
A (proper) vertex coloring of a graph is a labelling of the graph’s vertices with colors such that no two vertices sharing the same edge have the same color. A coloring using at most $k$ colors is ...
1
vote
0answers
23 views
Terminology: a notion of a set of “chords” for arbitrary subgraphs
I'm considering a problem on random graphs, where it makes sense to look the edges which "touch" a connected component, but which do not belong to it.
Consider a fixed graph $G$, where as usual we ...
2
votes
0answers
45 views
Terminology: is there a term for one order being on a geodesic between two others in the Cayley graph?
Think about the graph whose nodes are total orders on a finite set, and whose edges connect orders that only differ on two elements. This is actually a Cayley graph of $S_n$, but I don't want to fix ...
1
vote
2answers
147 views
What is a graph where edges are also vertices ?
Is there a name for a kind of graph where edges are vertices in the same graph ?
A example would be :
e1(a,b)
e2(c,d)
e3(e1,e)
0
votes
2answers
138 views
What is the “node weight” of a vertex?
I am reading a paper on weighted undirected graphs, and it states that if $A$ is the adjacency matrix of the graph $G$, then $a_{i,i}$ is the node weight of vertex $v_i$. What does this mean? Is ...
0
votes
1answer
80 views
Graph Theory - Clarification of type of graph
Just wondering if somebody can confirm the following:
If I have some number of verticies, if there is only one edge connecting two of the vertices, can this be a bipartite graph, or do all verticies ...
2
votes
1answer
109 views
Boolean circuits and digraphs
It is well known that connecting NAND gates allows the construction of arbitrary circuits. Furthermore, a NAND gate can be represented as a digraph with four vertices (in order, the two inputs, the ...
4
votes
2answers
70 views
Is the cycle graph $C_n$ defined only for $n \ge 3$?
I'm having a hard time seeing what $C_n$ would be for $n = 1$, or $n = 2$. Can someone clear up my confusion?
0
votes
1answer
91 views
Foam-like graphs
What's the "official" name of a connected planar graph consisting entirely of polygons (cycles), glued together at edges, e.g. - among other things - without "end vertices" (of degree 1) and without ...
3
votes
1answer
54 views
Uniform planar graphs?
What's the name of a planar graph in which every (inner) face has the same number $k$ of vertices? Something like $k$-uniform planar graph?
And is there a name for planar graphs in which every face ...
1
vote
1answer
165 views
Do the terms “quiver” and “meta graph” refer to the same concept?
Do the terms "quiver" and "metagraph" refer to the same concept? Or is there a distinction I am missing.
My sources are
Quiver - http://ncatlab.org/nlab/show/quiver
Metagraph - ...
2
votes
2answers
111 views
Terminology for operation where vertex is deleted and its parents/children are connected
I'm currently documenting an algorithm which involves deleting a node in a directed dependency graph while maintaining the implied dependencies between its parents and children.
Take for example the ...
1
vote
0answers
43 views
Bridge in a multigraph
According to Wikipedia, "a bridge in an undirected graph is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in ...
4
votes
1answer
70 views
Name for a type of subgraph that comes from identification of vertices?
Is there a special name for the kind of subgraphs you get by taking some sequence of the following operation: Pick two vertices and identify them so all edges going to either vertex get sent to the ...
0
votes
1answer
133 views
Name for a graph with two types of vertices $U, V$, where the end points of edges are either both in $U$, or one is in $U$ and the other in $V$?
I know that a graph whose vertices can be divided into two sets $U$ and $V$ such that every edge can only connect a vertex in $U$ to one in $V$ is called a bipartite graph. Is there a name for a type ...
0
votes
1answer
115 views
What does face-width mean?
What is the meaning of the term face-width? I have seen the term used as a property of an embedding of a graph on a surface. I haven't found a definition.
2
votes
0answers
43 views
Is there a name for the number of edges that need to be removed to lower the genus of a graph?
The number of edges that need to be removed from a graph to disconnect it is called the edge-connectivity. Similarly, given a graph of genus $n>0$, there is a minimum number of edges that you have ...
3
votes
1answer
27 views
On one quantity in a finite graph
Let $(G,E)$ be a finite undirected graph, and $d$ be the usual shortest path distance on $G$. The graph is not necessary connected, so $d(v',v'') = \infty$ if there are no paths from $v$ to $v'$. For ...
0
votes
1answer
463 views
A Set is a collection of well defined and distinct objects. What is a collection of well defined objects without being distinct called?
A set is a collection of well defined and distinct objects, considered
as an object in its own right.
What is the mathematical term for a collection of well-defined objects without distinction ...
2
votes
0answers
55 views
Is there are a name for a simplicial complex that is homotopic to the clique complex of its 1-skeleton?
A hollow octahedron is a nice triangulation of the sphere, because once you know the edges, you know everything. The vertices are obviously the ends of the edges, and the faces are any collection of ...
9
votes
3answers
190 views
Etymology of “topological sorting”
This may be a dumb question, but what's "topological" about topological sorting in graph theory?
I thought topology was related to geometry and deformations.
0
votes
1answer
91 views
Planar graph constructed from the edges of another planar graph
Let $G$ be a planar graph. We construct a graph $H$ from $G$ in the following manner :
The vertices of $H$ are interior points of the edges of $G$, one on each edge.
Two vertices of $H$ are joined ...
2
votes
2answers
103 views
Name for a bipartite graph in which one vertex set has maximal degree 1?
I'm looking for a specific name for a bipartite graph $(U,V,E)$ in which there is at most one edge incident to each vertex $u \in U$. That is, $|E_u| \le 1$ for all $u \in U$, where $E_u = \{(u,v) \in ...
2
votes
1answer
73 views
Shellable and Graphs
Suppose we have a graph $G$ of order $n$. Also suppose that we form the coloring complex $S(G)$ of $G$. What does it mean when we say that $S(G)$ is shellable?
2
votes
1answer
105 views
Eccentricity of a vertex
Eccentricity of a vertex $v$ in a graph $G$ is defined as max $\{d(v,w):w\in V(G), w\ne v\}$. My question is why is the word eccentricity used, what is the reason?
Thanks
2
votes
1answer
151 views
Does this matrix have a name?
If $L$ is a lower triangular matrix of ones, does the following matrix have a special name?
$$A = \left(\begin{matrix}L & -L \\
-L & L \end{matrix}\right)$$
1
vote
1answer
150 views
Term for a fully connected balanced graph (Rock paper scissor)
Is there a mathematical, graph theory, game theory term for a graph that is fully connected and balanced evenly with each other node.
I'm thinking in situations like Rock paper scissors where each ...
6
votes
1answer
2k views
Graph terminology: vertex, node, edge, arc
Precisely speaking, what is the difference between the graph terms of
("vertex" vs. "node") and ("edge" vs. "arc")?
I have read that "node" and "arc" should be used when the graph is
strictly a tree.
...
2
votes
2answers
85 views
Graph invariant that encodes number of subgraphs with $i$ vertices and $j$ edges
Suppose we have invariant of graph $G$ that tells us number of subgraphs with $i$ vertices and $j$ edges for every setting of $i$ and $j$. Is there a name for it?
I searched for "subgraph ...
3
votes
3answers
148 views
Name of an operation on graphs
Let $G$ and $H$ be two possibly directed, non necessarily simple, vertex-labelled graphs with respective adjacency matrices $A_G$ and $A_H$ and $V(G)=V(H)$.
1) What is the name of the graph $M$ with ...
2
votes
1answer
628 views
What are valent vertices?
Page 13 of Tropical Algebraic Geometry by Itenberg, Mikhalkin, and Shustin mentions 1-valent vertices, but I haven't been able to find a source that actually defines this term or managed to guess the ...
