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
17 views

Decompose a flow network into several trivial flows

Let $f$ be a flow in (a directed) network $G$. Show that it is possible to express $f$ as a sum of another flow $f_0$ which value is 0, and at most $|E|$ flows, each of which is trivial - i.e. flows ...
1
vote
0answers
64 views

Finding the Chromatic Polynomial for the wheel graph $W_5$

Let $G$ be a graph and let $k \in N$. The chromatic polynomial $P_G(k)$ is the number of distinct $k$-colourings if the vertices of G. Standard results for chromatic polynomials: 1) $G = N_n$, ...
1
vote
0answers
38 views

Graph with super nodes where each super node may have one or more sub-nodes in it

I have a question related to a problem I'm working on currently which is related to graph theory and complete sub-graph of size k (clique of size k). Let us say we have a graph where each node has one ...
1
vote
0answers
16 views

eccentrcity of vertices in the given graph

I was calculating eccentrcity of vertices of the following generalized Petersen graph $P(15,2)$. For the vertx $u_0$, vertices $u_6$ and $u_7$ are farthest at a distance 4 and for the vertex $v_0$ ...
1
vote
0answers
24 views

Shortest path in divisors graph

There is a graph with $N$ vertices numbered from $1$ to $N$. Edge between $a$ and $b$ exists if and only if $a | b$ or $b|a$. If $a|b$ then the weight of the edge is $\frac{b}{a}$. If $b|a$ then the ...
1
vote
0answers
42 views

Knowing number of nodes on a graph given depth and span

How can I know the maximum number of nodes in a graph, given that every node has degree K and that the graph has a diameter of at most ...
1
vote
0answers
12 views

Reference requests on SP -graphs to outline its research areas

I want to understand SP graphs (series-parallel graphs) deeper for more elegant computation. I want to understand which area to research to understand sp-graph deeper: logical formalism? Computational-...
1
vote
0answers
84 views

Weak, Regular, and Strong connectivity in directed graphs

There are 3 types of connectivity when talking about a directed graph $G$. 1) weakly connected - replacing all of $G$'s directed edges with undirected edges produces a connected (undirected) graph. ...
1
vote
0answers
30 views

Prove by induction a property of a tree graph

Prove by induction (and without the use of cycle definition) that if to delete a leaf vertex from a tree graph it will stay as a tree graph. I think Ive got it wrong but what I did is the following: ...
1
vote
0answers
39 views

Fermat's Little Theorem and graph cycle length

Let G be a digraph with $\mathbb{Z}_n, (n$ : prime) as its vertex set. We can define a permutation on G by multiplication by $a$ for $GCD(a,n)=1$ And let $l$ be the least natural number such that $a^...
1
vote
0answers
41 views

Supply/demand digraph - understanding problem

I'm dealing with multiflows and I found in "Combinatorial Optimization - Part C" by Schrijver in Chapter 70 a good source. The definition of the multiflow problem involves so-called supply- and demand-...
1
vote
0answers
59 views

Number of Hamilton paths in an extremely dense undirected simple graph

What is the fastest way (algorithm) to calculate the number of Hamilton paths in an extremely dense undirected simple graph (approximately 99.99% edges are connected)? I was thinking of the following ...
1
vote
0answers
24 views

Why is the eigenvector centrality considered a generalized version of degree centrality?

The eigenvector centrality of a vertex in a graph, is a self-referential centrality, which basically says that a vertex with a high value of eigenvector centrality is one that is adjacent to highly ...
1
vote
0answers
35 views

$K_3$ subgraph in a random graph

Consider a random graph of $n$ vertices where the probability of there being an edge between any two vertices is .01. I want to see what is the asymptotic behavior of the probability that ...
1
vote
0answers
90 views

Number of different Graphs with n vertices

A graph has 7 vertices and 7 edges. How many different graphs (non- isomorphic) are possible? The resulting graph has no constraints. i.e. it can be either connected or disconnected graph. How can I ...
1
vote
0answers
37 views

Crossing number of complete bipartite graph

I am looking for a proof of this inequality concerning the crossing number of a complete bipartite graph: $$ \textrm{cr}(K_{m,n}) \le \left\lfloor\frac{n}{2}\right\rfloor\left\lfloor\frac{n-1}{2}\...
1
vote
0answers
32 views

Distance $d$-independent set in hypercube

Given a graph $G = (V, E)$, a distance $d$-independent set is a subset $S \subseteq V$ such that any two vertices $x, y \in S$ have distance at least $d$. Thus traditional independent sets are ...
1
vote
0answers
224 views

Graph $2$-hops stable set

Let $D=(V,E)$ be a loopless digraph. We say that $S \subset V$ is $2$-hop stable if $S$ has these two properties: For each $u,v \in S$, the edge $uv \notin E$. Every vertex $s \in (V-S)$ can be ...
1
vote
0answers
36 views

Kőnig's lemma without a condition

Why does Kőnig's lemma not hold if we replace the condition that every vertex has a finite degree with the condition that every vertex has an infinite degree? Could you give a counter-example?
1
vote
0answers
32 views

Finding a maximum order degree-constrained subgraph

For a given (unweighted) graph G(V,E) with an integer d > 1, how do I find a connected subgraph H of G with maximum |V(H)| and satisfying ∆(H) ≤ d (i.e. subgraph H is connected with the maximum number ...
1
vote
0answers
128 views

Every connected component is a regular bipartite graph

Let $G = (S, T; E)$ a bipartite graph without isolated vertex, where $|S| \ge |T|$ and for any edge $st \in E$ $(s \in S$ and $t \in T$) $\deg(s) \ge \deg(t)$. How can I prove that $|S| = |T|$ and any ...
1
vote
0answers
33 views

Is it Possible to have an infinite number of divisibility graphs containing $K_5$ or $K_{3,3}$?

I came across this post: How does the divisibility graphs work? Where you can make a divisibility graph for any number n, using the method in the answer. Is it possible to have a divisibility graph ...
1
vote
0answers
51 views

Semigroup of matrices and expander Cayley graphs

I am interested in proving or disproving that certain Cayley graphs are expander. Let $S$ be the multiplicative semigroup of matrices generated by $A = \left( \begin{array}{cc} a & b \\ 0 & ...
1
vote
0answers
24 views

Maximizing the sum of the lengths of a walk in a directed acyclic graph (DAG)

You are given $V$ vertices and $E$ edges. Define a walk rooted in $s$ to mean a path obtained by starting from $s$ and following edges until you reach a node pointing to no other edges (this must ...
1
vote
0answers
10 views

How to find shortest path assigning weights to intermediate nodes

I met a problem to find shortest path for assigning multiple salesmen (m) to n cities. But in my problem, each city has an attraction factor/weight that it can be visited more than once if attraction ...
1
vote
0answers
47 views

Elementary graph theory questions (periodicity and strongly connected components)

Just going through some graph theory concepts and I have two elementary questions which must be pretty trivial (but sometimes what seems trivial to me turns out to be wrong, so I'd be happy if someone ...
1
vote
0answers
25 views

Show that we can choose bipartite subgraph

Given the graph: $$G = (V,E) \quad |V| = 2n, \quad |E| = m $$ Prove that in the graph $G$ we can choose a bipartite subgraph $G' = (V',E')$ with $ |E'| \geq \frac{mn}{2n - 1} $ I guess I have to ...
1
vote
0answers
221 views

A planar graph $G$ is the dual of its dual if and only if $G$ is connected.

That is, prove that a planar graph is the dual of it's dual iff it is connected. I know that in order for this to be true, G must be isomorphic to it's dual (G'), but I'm not sure how connectedness ...
1
vote
0answers
31 views

Concrete solution to the (oriented) Oberwolfach problem with one table

The oriented Oberwolfach problem (with only one table) and its solution are the following. In a meeting of $n$ people during $n-1$ days (combinatorists at Oberwolfach for concreteness), they all have ...
1
vote
0answers
28 views

Bipartite Graphs and perfect matchings

I'm trying to prove that if $G$ is bi-partite and $d$-regular for $d \geq 1,$ then $G$ has a one-to-one and onto matching between the two partitions of the graph. I have a feeling that I need to use ...
1
vote
0answers
108 views

Finding the exact value for $H(7)$

The graphs that I work with are all complete, each edge is colored red or blue, and each vertex is colored red or blue. $\textbf{Definition:}$ A graph is $\textit{Happy}$ if there exists a vertex ...
1
vote
0answers
59 views

Prove connected graph minus one vertex still connected.

Let G be a connected graph with at least two vertices. Prove that G has a vertex v such that if v is removed from G (along with all edges incident with it), the resulting graph is also connected. ...
1
vote
0answers
28 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
53 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
40 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
29 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
56 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 $|N(...
1
vote
0answers
81 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) = \sum_{i=1}^{J}x_{i}(t)w_{ij}...
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 $$d(\mathcal{F}):=\max\{k\in\mathbb{N}:\;\exists\,\...
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
32 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
40 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 $...