0
votes
1answer
16 views

Am I understanding Eccentricity, Radius and Diameter right?

Eccentricity, radius and diameter as defined in "Graph Theory and Complex Networks: An Introduction" (van Steen, 2010): Consider a connected graph G and let d(u,v) denote the distance between ...
0
votes
1answer
33 views

Graph Theory: What is the definition of the “Sorted Edge” algorithm?

I've been googling for a while and can't find a clear definition of the "sorted edge" algorithm--can anyone provide it please? A description would be helpful, but a simple statement of the algorithm ...
2
votes
1answer
47 views

Clear definition of degeneracy of a graph.

There are at least two questions on this topic but the answers are not clear to me and WiKi link didn't make it any clear either. Could someone please clarify is the degeneracy of a graph $G$ ...
0
votes
0answers
31 views

Depth in acyclic graphs

I am struggling to understand a definition in a paper: Given a acyclic (directed!) graph $D=(V,E)$ we define a sequence $Q_i \subset V(D)$ of sets: $$Q_0 = \emptyset,$$ $$ Q_i \textrm{ is ...
0
votes
1answer
60 views

Natural definitions of families of subgraphs

Cluster analysis is a vibrant area of applied mathematics, "used in many fields, including machine learning, pattern recognition, image analysis, information retrieval, and bioinformatics". A subfield ...
1
vote
1answer
49 views

Why do people not use “partially directed” graphs?

Are there structures in use which are a mix of directed and undirected graphs? I.e. the effective edge-set consists of both directed and undirected vertex pairs. In the case that the graph is simple, ...
4
votes
1answer
39 views

Transforming Nested Fixed-Point Formulas into Infinitary Logic Formulas with Finitely many Variables

There is a definition (actually a description of how it could be defined) of a fixed-point logic formula. The formula is in inflationary fixed point logic (IFP) in this case but it could also be ...
1
vote
1answer
46 views

Why is a graph an ordered pair?

From the source of all knowledge a graph is an ordered pair G = (V, E) comprising a set V of vertices or nodes together with a set E of edges or lines, which are 2-element subsets of V Why ...
0
votes
2answers
55 views

Minnor differences in notation used in definition of graphs

One of book states A graph G consists of two finite sets: a nonempty set V(G) of vertices and a set E(G) of edges, where each edge is associated with a set consisting of either one or two ...
2
votes
1answer
33 views

definition clarification in graph theory

I was studying about Almost Self-Centered Graphs (ASC). ASC graphs are introduced as the graphs with exactly two non-central vertices. Of course, the remaining two vertices are diametrical. My doubt ...
1
vote
0answers
41 views

Subgraph without “holes”

does everyone know, if there already exists a definition of subgraphs, which do not contain a "hole"? EDITED: That means: I presuppose a planar embedding of a graph G and I want to find a connected ...
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
1answer
39 views

doubt about my last question

I have a very basic doubt. If we talk about rooted graph, can we consider any graph whose one vertex is labeled in a special way to distinguished it from other vertices or only rooted tree. this doubt ...
3
votes
2answers
130 views

to clear doubt about basic definition in graph theory

Can anybody help me in clearing the doubt about hierarchical product of graphs. Its quite different from other graph products. Here is the screenshot and link how it is done. I know the rooted graph, ...
0
votes
1answer
98 views

question about Graph Theory notation

I'm just starting to learn graph theory. I have two questions about notation: 1). For a graph $G$ we denote the vertex set $V$ and the edge set $E$ by $G=(V,E)$. So we have a graph $G=$ ...
1
vote
1answer
139 views

Anonymous graphs and graph embeddedness

What are anonymous graphs, what is graph embeddedness, and how do they relate to each other? Very confused - I could not find short answer. Thanks.
1
vote
0answers
84 views

Which cut does the “minimum cut” refer to?

My course notes give the following definitions; could someone please verify that the last definition is non-standard? (I've spent all evening googling, and isn't "minimum cut" a concept related to cut ...
2
votes
0answers
135 views

Are edge cuts, vertex cuts, and cut sets all variously called “cuts”?

I've seen "cut" being used to refer to all three, in different places, and sometimes in the same book. Which does "cut" most commonly refer to? p.s. I am aware that "cut" itself can be defined to ...
1
vote
1answer
100 views

Prüfer sequence for an order-2 tree?

All the algorithms for constructing a Prüfer sequence state that the input is a tree, but none give any output corresponding to an order-2 tree. And Wikipedia gives this definition:" A Prüfer ...
3
votes
1answer
25 views

What is the name for the unique “simplification” of a graph?

Is there a conventional name for the resultant graph (H) obtained by deleting all loops and multiple edges from the original graph (G)? Something along the lines of "Let H be the simple graph of G.." ...
2
votes
1answer
107 views

how to write the process of decomposition of a graph into shortest closed sub graphs

If I want to decompose a graph in to possible shortest closed cycles (as shown in right side). then how can i describe this process with mathematical notations. to understand please refer below ...
0
votes
1answer
228 views

Mathematical notation of graph subdivision

If anyone can define a directed graph subdivision with mathematical notation, please post a response. My second question is: Irrespective from the planar embedded graph or not, is this definition ...
1
vote
1answer
52 views

What is the graph $K^c_m$?

The book "Graph Theory with applications" by J.A. Bondy and U.S.R. Murty, which is available here. The Theorem $4.6$ of this book says that: If $G$ is a non-Hamiltonian simple graph with $n≥3$ ...
0
votes
1answer
100 views

Operations with planar graphs

I think in the graph theory operations such as decomposition into cycles, union, intersection, difference, subdivision can be done. If I am given a planar graph (for e.g. see figure), then can the ...
3
votes
0answers
66 views

Define composition of small cyles and making a big graph

I am having following sub graphs and wish to compose all and make a one bigger graph (say G). After that, I want to select the closed path where it is passing along the outer vertices of that ...
0
votes
1answer
188 views

Different formulation of a Traveling Salesman Problem

Given a undirected, weighted, complete graph $(V,E,c)$ with $c \to \mathbb{N}$ and $v_0 \in V$ we are looking for a set $E' \subset E$ minimal with respect to $c$ with the following conditions: for ...
1
vote
1answer
79 views

How do we distinguish “walks” or “paths”?

For example, let $G(V,E)$ be a graph such that $V=\{v_1,v_2\}$ and $E=\{(v_1,v_2)\}$. And let $s_1:\{1,2\}\rightarrow V$ be a walk such that $s_1(1)=v_1$ and $s_1(2)=v_2$. And let ...
0
votes
1answer
45 views

What is this matrix called?

Let $G=(V,E)$ be a finite graph where $V$ has $n$ elements so that $V=\{v_1,...,v_n\}$. Now, define $a_{ij}$ to be 1 if $(v_i,v_j)\in E$ and 0 otherwise. What is this $n\times n$ matrix $(a_{ij})$ ...
1
vote
1answer
143 views

Does *pair* always mean a pair of distinct elements in graph theory?

Definition of edge in wikipedia: An edge of a graph is a set of 2-elements in a set of vertices. Definition of tournament in my text: A tournament is a directed graph such that each pair of vertices ...
1
vote
1answer
504 views

Definition of induced cycle

According to Diestel (page 4): "If $G' \subseteq G$ and $G'$ contains all the edges $xy \in E$ with $x, y \in V'$, then $G'$ is an induced subgraph of $G$" According to Wikipedia "induced cycle is a ...
2
votes
0answers
83 views

Graph Theory: Help with a definition

I need some help to see if the definition I found of Cycles and Cycles Decomposition is right, here it is: A graph is a Cycle if it is isomorph to another graph $G=(V,E)$ with the following ...
2
votes
1answer
378 views

bipartite graph - sufficient and necessary conditions

Sorry for a silly question, I got confused with the definition of bipartite graph. What is a necessary and sufficient condition for a bipartite graph. ...
1
vote
2answers
97 views

Number of Vertices of Graphs

So, I was looking at some graph theoretical stuff, more specifically Topological Graph Theory, and I had a question about the definition of graphs: is there usually a condition in the definition ...
1
vote
0answers
23 views

Definition of Chromatic class digraph of a m-coloured digraph

I have to prove that if $D$ is a m-coloured digraph, then $K(D) = K\big(C(D)\big)$ Where $C(D)$ is the chromatic transitive closure of $D$, which is a multidigraph with the same nodes and arcs of $D$ ...
3
votes
0answers
50 views

Defining a Certain Class of Plane Graphs

I'm having problems finding the right words to formulate the following class of graphs in a definition. I'm defining a class of plane graphs with the following properties: Removing any vertex of ...
5
votes
1answer
523 views

Understanding various definitions of TREE($n$) in Friedman's finite form of Kruskal's tree theorem.

I was reading the Wikipedia article on Friedman's finite form of Kruskal's tree theorem, and am interested in the large numbers TREE(n). I would like to verify TREE(2)=3 myself, but find conflicting ...
1
vote
1answer
244 views

What is the definition of an induced cut

I am reading A simple min-cut algorithm (Stoer & Wagner, 1997), and the proof uses some terms I don't understand. Specifically I am unclear on what is meant by "$C_v$ the cut of $A_v \cup \{v\}$ ...
2
votes
1answer
45 views

Reducts of categories

There are several ways to reduce a category. The skeleton of a category is the category with isomorphic objects collapsed into one i.e. the only isomorphisms that remain are the identities. What's ...
1
vote
1answer
174 views

What does unique “minimal” partition mean (Context: Partitioning of Vertex-Sets)?

I am studying R. Diestel's Book Graph Theory and I encountered a formulation which I don't quiet understand. Mr. Diestel speaks in this proof on page 180 (Google Books Link) in the second last line of ...
1
vote
1answer
337 views

What is a “mixed graph”?

I'm working on a digraph problem in which bidirectional edges need to be treated separately. As such, we could consider them as undirected edges. Clearly, if I replace bidirectional edges with ...
1
vote
3answers
103 views

Should one think of a network as a connected graph ? (Or: What is the right way to think of a network?)

In the definition of a network, are we only considering connected graphs ? Because I keep encountering definitions that don't assume explicitly that we deal with connected graphs, but which would be ...
8
votes
3answers
898 views

Is the empty graph connected?

Is the empty graph always connected ? I've looked through some sources (for example Diestels "Graph theory") and this special case seems to be ommited. What is the general opinion for this case ? As ...