Use this tag for questions in graph theory. Here a graph is a collection of vertices and connecting edges. Use (graphing-functions) instead if your question is about graphing or plotting functions.

learn more… | top users | synonyms

1
vote
0answers
27 views

Showing that a graph is still k-connected when adding a new vertex.

I need help with the following homework question: Given a $k$-connected graph $G$, let $G'$ be obtained fro $G$ by adding a vertex $x$ and connecting it to $k$ vertices of $G$. Show that $G'$ is ...
1
vote
0answers
49 views

How to show that deleting at most $(m-s)(n-t)/s$ edges from a $K_{m,n}$ will never destroy all its $K_{s,t}$ subgraphs.

This problem is from Graph Theory by Diestel Chapter 7 (Extremal Graph Theory) section 5 (regularity lemma) problem 9. I was thinking about applying the Erdos & Stone theorem, but I am honestly ...
1
vote
0answers
39 views

Expected number of vertex-pairs without any simple path in between

Consider a random undirected graph $G(n, p)$, with $n$ vertices and each edge is added independently with probability $p$. The goal is to find the expected number of vertex-pairs without any simple ...
1
vote
0answers
28 views

Probability having a path of length less than a fixed number

A graph $G(V, E)$ is given. For a random pair of nodes $e_1, e_2 \in V$, what is the chance/probability of having a path of size less than $k$ (a fixed number) between $e_1$ and $e_2$ (let's assume ...
1
vote
0answers
24 views

outerplanarity of grid graph

I was asked to compute the outerplanarity of (n x m)-grid graph where a given hint was "a grid doesn't need to be drawn as a grid. There are also other ways to draw it!". So, I tried to redraw a 4x5 ...
1
vote
0answers
23 views

Is there any maximum for number of vertices of a k-tree?

Is there any upper-bound for number of vertices we can add to a k-tree with $k+1$ vertices so that the resulting graph be also a k-tree? We now each new vertex can connect only with $k$ vertex of ...
1
vote
0answers
19 views

Eccentricity of vertex in a permutation cycle graph

The permutation cycle graph is defined as follows. Permutation Cycle Graph: A permutation cycle graph for a given permutation $\pi$ of a finite set $V$, is its cycle graph $\Gamma$ such that ...
1
vote
0answers
24 views

Is my binary search tree correct?

I must construct a binary search tree for the predefined identifiers in the order of ORD, CHR, WRITE, SEEK, PRED, EOF, WRITELN, BOOLEAN, PAGE, GET, TRUE, COPY, POT, ABS I am thinking I got it right ...
1
vote
0answers
55 views

Graph Theory: Are Infinite Trees Planar?

Graph theory: Are infinite trees planar? I think countable trees are, but not uncountably infinite trees, apparently. How does one construct such a tree?
1
vote
0answers
53 views

Prove that the bipartite graph can be covered by disjoint k-stars

Let $k$ be a natural number with $k \geq 2$. Consider a bipartite graph $G$ with vertex classes $A$ and $B$, with $|B| = k|A|$. Use Hall's Theorem applied to a suitable graph $G'$ to show that if ...
1
vote
0answers
77 views

Finding all eigenvalues of the adjacency matrix of a simple graph

I want to find all eigenvalues of the adjacency matrix of the following graph(Graph spectrum), where $G$ and $H$ are complete graphs with $n$ and $m$ vertices, respectively, for positive integers $n,m ...
1
vote
0answers
59 views

Neural Networks - Hopfield Net Dynamics

In the book by K.Du, "Neural Networks and Machine Learning", Springer, 2014, p.159", the Hopfied dynamics equation (in discrete network model) is given as $$net_{i}(t+1) = ...
1
vote
0answers
39 views

Why find triangles in graphs?

Given a graph, there are numerous algorithms out there to find a set of 3 vertices such that a triangle exists, but why is this topic studied? What are the applications? The advantages? The problems ...
1
vote
0answers
16 views

Measuring disjointness of decompositions of a countably infinite set

Let $n\in\mathbb{N}$ be fixed. Given a family $\mathcal{F}$ of subsets of $\mathbb{N}$, each of size $n$, with $\bigcup\mathcal{F}=\mathbb{N}$, set ...
1
vote
0answers
23 views

What graphs are “unavoidably” Hamiltonian?

When we try to find a Hamiltonian cycle in $K_{n,n}$, we can start at a vertex, go to any neighbouring vertex, then any neighbouring vertex unused so far and so on. Whatever choices we make, we never ...
1
vote
0answers
31 views

Not isomorphic graphs with same spectrum - exists?

I am wondering if there exists two graphs, which are not isomorphic with the condition that both of them have the same spectrum. Two graphs are isomorphic when they may be drawn in the same way. ...
1
vote
0answers
38 views

eigenvalue of adjacency matrix of bipartite graph

let $m$ be a eigenvalue of adjacency matrix of bipartite graph and $(x,y)$ be eigenvector of corresponding to $m$. why can be $ (-x,y)$ eigenvector of adjacency matrix? how can we find $(-x,y)$ ...
1
vote
0answers
19 views

Geodesics is a connected graph. (Ex. 1.16 in A First Course in Graph Theory by Chartrand and Zhang)

The problem I am trying to solve is the following. Let $P = (u=v_0,v_1, \cdots ,v_k = v),k\geq 1$,be a $u-v$ geodesic in a connected graph $G$. Prove that $d(u,v_i) = i$ for each integer $i$ with ...
1
vote
0answers
109 views

Definition: is a graph allowed to have a “dangling” edge without a vertex at its end(s)?

My textbook gives the following definition "a graph $G=(V,E)$ consisting of $V$, a nonempty set of vertices and $E$, a set of edges. Each edge has either one or two vertices associated with it." Now ...
1
vote
0answers
62 views

[ Determinant of Adjacency Matrix is null ]

Let be $D=(V,E)$ . Prove then the determinant of its adjacency matrix , $det(A) = 0$ $\iff$ $\exists S \subseteq V $ such that $|v_{ext} \cap S|$ is an even number , $\forall $ v $\in V$ . $v_{ext}$ ...
1
vote
0answers
15 views

Shortest Walk on Graph with Modular Vertex Weights

Please bear with me as I establish some notation to make posing this question much easier! Let $X = (V, E) = (\{x_1, ..., x_n\}, \{(x_i, x_j)_{i, j \in I \times J}\})$ (where $n \in \mathbb{N}$, $I, ...
1
vote
0answers
101 views

maximum matching to solve a path-packing problem

G=(V,E) is a directed graph. . A path packing of G is a collection of paths: $\cal{P}=\{ P_1,\dots P_k\}$ such that $V(P_i)\cap V(P_j)=\emptyset$ $\forall i,j$ s.t. $ 1<i<j<k$ where ...
1
vote
0answers
40 views

Finding a Hamiltonian cycle for $Q_4$

A hyper cube $Q_n$ is a graph that have the length-n binary sequences as its vertices. Two vertices are adjacent if they differ in one entry. I found a Hamilton cycle for $Q_3$ as follows $$000 \to ...
1
vote
0answers
34 views

How many variables can be pairwise anticorrelated

I am working on a computational project involving analysis of data. Each item of data that I have has a few hundred attributes; I have several million items of data. The attributes are essentially ...
1
vote
0answers
44 views

Are these graph coloring algorithms equivalent?

Suppose you want to color the vertices of a graph in a greedy fashion, given a predetermined order of these vertices. I am wondering if these two algorithms are equivalent: Algorithm 1: Consider ...
1
vote
0answers
26 views

Independence of three events

Let $G$ be a graph with three vertices $u,v,w$. Moreover, each vertex has a real-valued label $l(d) \in \mathbb{R}$ for $d$ in $\{u,v,w\}$. Now let $b(x) = \lfloor \frac{x-u}{\delta} \rfloor$ for $x ...
1
vote
0answers
97 views

Show that $T(n) = 4 × T (n - 1) - T(n-2)$…

$T(n)$ is the number of spanning trees for the n-ladder. Show that $T(n) = 4 × T (n - 1) - T(n-2)$. -My teachers hint was to first show $T(n) = 3×T(n-1) + 2×T(n-2) + 2 × T(n-3) + ... + 2× T(2) + 3 × ...
1
vote
0answers
49 views

Difference between k-coloring and k-colorable?

We say that a graph $G=(V,E)$ has a $k$-coloring if each vertex can be assigned a color in $\{1,...,k\}$ so that no edge has two vertices of the same color. Then, am I right in saying that if a graph ...
1
vote
0answers
26 views

How to create a dense graph, when each node has a limited number of edges?

I am working on an application that needs to connect $n$ disconnected nodes, where each node can have at most $m$ edges, such that when traveling from the $ith$ node in graph to the $jth$ node, the ...
1
vote
0answers
49 views

When the size of minimum edge cover is equal to the size of maximum independent set?

We know that the size of the minimum edge cover is always equal to or greater than the size of the maximum independent set of the same graph. I want to know is there any special type of graphs that ...
1
vote
0answers
47 views

Generalization of Euler tour to higher dimensions

Happened to be I needed a theorem stating that any 2-dimensional regular CW complex having the property that each of its 1-cells is attached to even number of 2-cells can be decomposed into ...
1
vote
0answers
57 views

Clustering large biregular graphs

I have a bipartite graph $G=(U,V,E)$ where: Every vertex in $U$ has degree $C$ Every vertex in $V$ has degree $R$ $\left|U\right|=(K\cdot R)$ $\left|V\right|=(K\cdot C)$ More succinctly, its a ...
1
vote
0answers
43 views

chromatic number in a “duo-planar graph”

For the purposes of this task, we will call a "duo-planar" graph, a graph that has been made of joined two planar graphs. More precisely, G is duo-planar, when $E(G)$ can be divided into two sets ...
1
vote
0answers
18 views

Canonical forms for matrices with binary elements.

Based on this answer to a combinatorics question I grew curious of results regarding similarities or canonical forms of matrices fulfilling these criteria: Elements of matrix are binary valued ...
1
vote
0answers
13 views

Wouldn't the asymptotes of the 2D projection of the inverse of the Riemann Zeta function show the real part of all the non-trivial zeros?

Can somebody provide a visualization of $z=\frac{1}{\zeta(x+iy)}\pm N$ for some large $N$ projected onto the $xz$-plane? I would imagine that if we found any asymptotes converging anywhere other than ...
1
vote
0answers
30 views

Find subgraph with maximum number of edges

Suppose there is a simple graph G. Is there a way to find a subgraph with a maximum of edges, for a certain number of vertices m?
1
vote
0answers
36 views

Probability Assessment of Interactive Markov Chain (IMC)

Firstly, consider a Markov chain in your mind. Probability of each state of the Markov chain can be obtained by following Chapman–Kolmogorov equation. $$ P(n\Delta t) = M^{n}P(0) $$ where P is the ...
1
vote
0answers
122 views

$(r+1)$ Clique of Induced subgraph and Turan’s theorem

$G$ is a $s$ regular graph. $A$ is a set of vertices where $|A| = s$ and $A \subseteq G$. $E$ is the number of edges of $G$. $n$ is the total number of vertices of $G$. Problem: Find the lower ...
1
vote
0answers
44 views

Graphs with disjoint edge sets

Consider a fixed set of vertices $\{v_1,v_2,\ldots,v_m\}$ and a family of graphs $G_1, G_2, \ldots, G_n$ on these vertices such that no two graphs share an edge. In other words, if $E(G_i)$ is the ...
1
vote
0answers
21 views

Yet another curious convolution

Some time ago, I found the following algorithmic problema: Count the number of distinct unrooted, unordered, labeled trees of $n$ nodes where each node has at most $k$ neighbors. Given that the ...
1
vote
0answers
37 views

Expected number of random sub-cliques neccessary to cover a complete graph

I have the following problem: Given a complete, simple graph, i.e., a graph $(V,E)$ where every possible edge is realized, so $|E| = \frac{|V||V-1|}2$. Now consider complete sub-graphs, or ...
1
vote
0answers
41 views

Is there a name for this particular kind of tree graph?

I've recently encountered a problem which heavily involves analysis of structures analogous to weighted trees with no nodes of degree two (such a node along with its adjacent edges would be ...
1
vote
0answers
88 views

The Earth-Moon Map Problem

The following is the Sulanke Earth-Moon Map. A planet and moon have each been divided into eleven contiguous regions. In both maps, the regions 1-3, 3-5, 5-2, 2-4, and 4-1 do not touch, while all ...
1
vote
0answers
32 views

Binary Minimum Spanning Tree (from complete graph)

Given a weighted complete graph (or more exactly, a matrix of pairwise metric distances between vertices), I need to find a good approximation of the binary spanning tree of lowest total cost. There ...
1
vote
0answers
34 views

On the LowerBound for the number of edges of a simple connected graph on $n$ vertices.

We know that if $G$ is a simple graph on $n$ vertices and if $G$ has $k$ components then the number of edges $m$ of $G$ has the lower bound: $n-k\leq m$. The proof of one of a reference book on ...
1
vote
0answers
31 views

What kind of topological sorting exists in graph theory and what are their graphic plotting?

I know that there is at least two kinds of topological sorting: "by rank" and by"level" a level of a vertex is the maximal length of a path with x as an extremity. a rank of a vertex is the maximal ...
1
vote
0answers
21 views

Name of operation: changing the root of a rooted tree

What is (if any) the name of the operation of changing the root of a rooted tree? Picking a vertex which is not the root, then reorienting the edges in such a way that the vertex becomes the root?
1
vote
0answers
37 views

Graph having bounded degree

A graph is said to have bounded degree if there exists $N \in \mathbb{N}$ such that, for every $x \in V$, one has $\sum\limits_{y \in V} A_{x,y} \le N$. Show that, in this case, for any $f \in ...
1
vote
0answers
52 views

Degree/diameter problem for the even girth case

Let $G$ be a graph with girth $g$, minimal degree $\delta$, maximal degree $\Delta$, and diameter $D$. Define $$n_0(g,\delta) := \begin{cases} 1 + \delta + \delta(\delta-1) + \cdots + ...
1
vote
0answers
30 views

Proof of properties of paths with distinct parities

I'm trying to work on this theorem, but I can't reach anywhere. Let $P$ and $Q$ be paths in a graph $G$ such that the end of $P$ is the same as the beginning of $Q$. Let $u$ be the first vertex ...