# Tagged Questions

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 ...
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 ...
42 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$ ...
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 ...
59 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 ...
47 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, ...
37 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 ...
45 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 ...
52 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 ...
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 ...
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 ...
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? ...
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 ...
129 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, ...
96 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=$ ...
134 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.
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 ...
132 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 ...
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 ...
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.." ...
105 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 ...
218 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 ...
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$ ...
99 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 ...
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 ...
187 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 ...
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 ...
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})$ ...
142 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 ...
492 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 ...
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 ...
370 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. ...
96 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 ...
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$ ...
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 ...
515 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 ...
239 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\}$ ...
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 ...
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 ...
333 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 ...
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 ...
869 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 ...