0
votes
1answer
25 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
19 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
24 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
25 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
29 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
37 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
40 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
128 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
29 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
31 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
14 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
70 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
23 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
84 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
1k 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
18 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
53 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
52 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
109 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
43 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
108 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
78 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
82 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
64 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
150 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
64 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
363 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
32 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
320 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
59 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
57 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
129 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
97 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
284 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
158 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
259 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
84 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
77 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
151 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
54 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
42 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
26 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
47 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
168 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
681 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
182 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
124 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
71 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?