Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [graph-theory]

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.

0
votes
0answers
7 views

Constrained Graph Optimization - Algorithm to connect thousands of nodes while minimizing cost for bus routing?

I'm trying to make public transportation better by working with my city to rearrange the bus routes to minimize travel time for users with certain constraints - up to b buses and k kilometers of ...
1
vote
0answers
12 views

Number of X3SAT Instances

Exactly 1 in 3SAT (X3SAT) is a variation of the boolean satisfiability problem. Given a 3CNF instance is there a satisfying assignment where exactly one literal in each clause is true? X3SAT is known ...
0
votes
0answers
10 views

Implementing the Optimal Non-Bipartite Matching

In one of my research works, I needed to implement the optimal non-bipartite matching of a graph with vertices in an Euclidean space, which I describe in more details below: Suppose that $n$ points ...
0
votes
0answers
20 views

Mapping the cycle graph into the real line

I am trying to work on the following exercise. Suppose $f: (C_n, d_n) \to (\mathbf{R}, |\cdot|)$ is a map of the cycle graph $C_n$ (with nodes labelled, $1, 2, \dots, n$) with the shortest path ...
1
vote
0answers
18 views

Is there a Hamiltonian path? (i.e. can the general associative law be solved with Graph Theory?) [duplicate]

Consider the different bracketings of the summation $$1+2+3+4+5\,.$$ I've listed them all below: $$ 1+(2+(3+(4+5)))\,,\quad (1+((2+3)+4))+5\\ 1+(2+((3+4)+5))\,,\quad (1+(2+(3+4)))+5\\ 1+((2+(3+4))+...
1
vote
0answers
22 views

Existence of a path consisting of only essential/inessential vertices

When learning definition of essential and inessential vertices, out of curiosity, I am looking for a graph which contains a path that only consists of essential/inessential vertices. A vertex is ...
2
votes
1answer
35 views

Generating function for number of graphs with all vertices of degree 1 or 2

To elaborate on the title, I am trying to find the exponential generating function for $\{a_n\}_{n \geqslant 0}$, where $a_n$ is the number of graphs on $n$ vertices with an odd number of connected ...
1
vote
1answer
22 views

Prove that a simple connected graph with exactly 2 cut vertices has a cut edge

I'm trying to prove that a connected simple graph that has exactly 2 cut-vertices has a cut edge. My attempts at proving this are to somehow show that the two cut vertices are adjacent, which would ...
1
vote
3answers
29 views

Given a simple graph and its complement. Prove that either of them has a cycle.

I want to prove that when given two graphs $G$ and $\bar{G}$ (complement), at least one of them must contain a cycle. I thought about showing it by the number of edges: Suppose $G$ and $\bar{G}$ ...
1
vote
2answers
18 views

G=(V,E) a graph that that maintains this condition $\left |E \right |\geq \left | V \right |\geq \left |3 \right |$ must have a circle

Condition : $\left |E \right |\geq \left | V \right |\geq \left |3 \right |$ and graph G=(V,E). I need to proove it without using any graph theorems and lemmas(if so then I have to proove them). I ...
0
votes
0answers
22 views

Minimum number of edges in a graph for which adding any new edge increases the number of copies of $K_{10}$.

Question 5 from The Probabilistic Method by Alon and Spencer. Let $G$ be a graph on $n\geq 10$ vertices such that the addition of any edge not yet in $G$ increases the number of copies of $K_{10}$ in ...
0
votes
0answers
38 views

Find the mathematically correct formulation for the following …

I would like to explain mathematically formally that there are two nodes and that the subgraph of the one node is the same as the subgraph of the other node (see figure). AND That there are two nodes ...
0
votes
0answers
16 views

Graph Theory - Line and Ring network line efficiency [on hold]

I understand the link efficiency is $\frac{m - avearge\_path\_length(G)}{m}$, where $m$ is links of Graph $G$. Why does a Line and Ring network has link efficiency of $\frac{2n-4}{3(n-1)}$ and $\...
1
vote
0answers
23 views

Distributions of components in random geometric graphs

In the context of random geometric graphs where edges are assigned according to a distance criterion $d_{ij}\le \delta,$ with $d_{ij}$ denoting the Euclidean distance between the vertices $i$ and $j,$ ...
1
vote
1answer
35 views

How can I get maximum number of vertices if I already know edges

If I already know edges how can I get the maximum number of vertices? Question: There is a graph that has $36$ edges, and where every vertex has degree at least $5$. What is the maximum number of ...
1
vote
1answer
58 views

Combinatorial Sum equals $2n^{n-3}$

For $n \ge 3$, prove or disprove that \begin{equation} \sum_{m = 1}^{n-1} {{n-2}\choose{m-1}} m^{m-2} (n-m)^{n-m-2} = 2n^{n-3}. \end{equation} I was trying to do this problem, and I managed to ...
0
votes
0answers
20 views

Given graph $G$ that is “close” to another graph $G'$ can we find certain bipartite subgraph of $G$

Suppose that $G$ is a graph with $2n$ vertices and $n^2$ edges. Let $\epsilon>0$. We say that $G$ is $\mathbf{\epsilon-close}$ to $K_{n,n}$ if $$\frac{|E(G)\triangle E(K_{n,n})|}{\binom{2n}{2}} \...
5
votes
0answers
43 views

Network Connectivity Problem

Assume a network (a complete undirected graph) comprised of $N$ participants (vertices). Each person holds a different piece of information, unknown to all other members. The participants can ...
1
vote
0answers
11 views

An (sort of) inverse Dirichlet problem

Let $G = (V, E)$ denote the $n \times n$ integer grid, with the natural boundary $\partial V$. If $f$ is any real valued function defined on $\partial V$, then it is well known that $f$ can be ...
0
votes
1answer
16 views

Laplacian of a directed weighted graph

I know that for a simple undirected graph $\mathcal{G}(V,E) $ the Laplacian matrix $L$ is defined as: $$ L:=D-A$$ where $D$ is the degree diagonal matrix and $A$ is the adjacency matrix of $\mathcal{G}...
0
votes
0answers
8 views

Schedule feasibility graph

I have a scheduling problem of this type: a set $E$ of events $e_1, e_2, \dots, e_n$, I have to determine if a schedule $T : E \rightarrow \mathbb R^+$ exists with constraints of both type $T(a)-T(b)\...
0
votes
0answers
19 views

What conventions are there for notating graph labels?

So I'm writing a paper and I want I often find myself needing to somehow notate the label of a vertex or edge. For example I may need to write some condition that determines if a vertex in a graph ...
2
votes
0answers
22 views

How to randomly sample a social graph to find paths between at least 20% of profiles?

Given a Graph, where we know Total number of nodes (~100,000) Average no of connections per node (~200) Maximum distance between two nodes (~5) How many nodes (and its connections) do we have to ...
2
votes
1answer
72 views

No. of ways to put 1's in exactly K cell of 2*N grid such that no two 1's cell share adjacent side

Its not like coloring of 2*N grid with m colors. Here I need to calculate number of ways to put 1's in exactly K cell of 2*N grid such that no two cells containing share adjacent side. Ex : for n = 4 ...
1
vote
0answers
21 views

Finding Components in Complement of Graph

Consider a graph G having N vertices. For each vertex, I am given adjacency vector, denoting the elements adjacent to vertex in G. For example say :- N = 4, and adjacency matrix is like : [1] = {3,...
1
vote
1answer
29 views

Let G be a graph with n vertices where every vertex has a degree of at least n/2. Prove that G is connected.

I'm trying to prove this by contradiction. So, I'm assuming that the graph is not connected. But even if the graph is not connected, I believe it will still have n/2 degree vertices. I'm finding it ...
1
vote
0answers
8 views

maximum number of perfect matchings of $K_{2n}$ such that no edge appears in two different matchings

Given a complete graph $G=K_{2n}$, construct a set $P$, such that each element $p$ of $P$ is a perfect matching of $G$ and every two elements $p_i,p_j$ don't share a common edge of $G$.What's the ...
5
votes
1answer
23 views

Writing cycles of a graph as a linear combination of fundamental cycles

It is folklore that the fundamental cycles (corresponding to aparticular spanning tree) of a graph constitute a basis for its cycle space, while the proof uses the linear indepence of fundamental ...
0
votes
0answers
22 views

Network Optimization [on hold]

Suppose that after solving a shortest path problem, you realize that you underestimated some arc lengths and overestimated some other arc lengths. The actual arc lengths are c'_ij instead of c_ij for ...
0
votes
0answers
9 views

What is the graph required propertier or prove that it does not exist? [on hold]

In each case below, either draw a graph with the required propertiesenter image description here or prove that it doesn’t exist (a) A connected graph without loops or multiple edges and with 5 ...
-1
votes
0answers
21 views

Network Optimization Problem [on hold]

We define an in-tree of shortest paths as a directed in-tree rooted at a sink node t for which the tree path from any node i to node t is a shortest path. State a modification of the generic label-...
1
vote
1answer
35 views

How to decide whether a linear subspace over $\mathbb{Z}_2$ is the cycle space of some graph?

Preliminaries: Assume we have a simple graph $G=(V,E)$ (no loops, no multiple edges). If we label the edges with $k=1,\dots,|E|$, its cycle space $C$ can be identified with a linear subspace of $\...
1
vote
0answers
13 views

Set of hyperplanes to polyhedron topology

Problem By intersection of a set of planes (in three-dimensional space) I constructed an edge-vertex topology structure (see image). I was able to reconstruct the polygons in this structure by ...
0
votes
2answers
23 views

How can I represent that all element has some property?

I want to represent mathematically that all elements $v \in V$ has $x$ and $y$ properties. I tried: Consider a graph $G=(V,E)$ where $\forall v \in V(G) \Rightarrow x[v] \in \mathbb{R} \space|\...
3
votes
0answers
41 views

Could Galois theory be somehow applied to graph theory?

In Galois theory, we are to discuss about splitting field $\mathbb{Q_f}$ of a polynomial $f\in \mathbb{Q}[x]$ and build correspondence between the galois subgroup $H\leq Gal(\mathbb{Q_f/Q})$ and a ...
1
vote
0answers
23 views

Official name of the problem of sum of edge squares of a graph $G$

Given a graph $G=(V,E)$, a $1-1$ mapping $f:V\rightarrow\{1,2,...,n\}$ is called a proper numbering of G. Then we know, for a proper mapping $f$, the edgesum of the $s_f(G)$ produced by $f$ is defined ...
1
vote
0answers
24 views

Weak convexity in graphs

As we know, a finite undirected graph induces a metric space on the set $V$ of its vertices. A convex set of vertices is defined as a set $S \subseteq V$ such that for any $u,v \in S$, all shortest ...
0
votes
1answer
39 views

dead simple arbitrage algorithm

When googling for a solution to the currency arbitrage problem, a variant of the Bellman-Ford algorithm comes up as the most efficient solution. See for example this page or this stackexchange post. ...
0
votes
0answers
29 views

Generalizable combination of combinations ratio equation

I have been trying to solve the following problem for a few days and any help or direction towards combinatorics literature would be appreciated. Given a starting sequence of length n, an index ...
1
vote
0answers
16 views

Distinct 1-factors which intersect i edges in a graph

I have been thinking for a long while on this question: Let i be a fixed integer where 1 ≤ i ≤ n−2. Given the graph Kn,n write down a formula for the number of ways you can choose a pair of distinct 1-...
-2
votes
0answers
24 views

Vertex of Valency One [on hold]

Say I have a connected graph with twelve vertices and eleven edges. Does it have a vertex of valency one?
0
votes
1answer
28 views

Find a largest graph with ten vertices, such that each vertex has even degree.

I've been trying to find the largest graph with 10 vertices such that each vertex has even degree. If the number of vertices, say $n$, were odd, then the answer is clearly just the complete graph $K_n$...
0
votes
1answer
19 views

Laplacian matrix of the weighted graph

The weighted Laplacian matrix element is given by \begin{align} L_{ij} \; = \; \Big( \sum_{k} w_{ik} A_{ik} \Big) \, \delta_{ij} - w_{ij} A_{ij} \end{align} $A_{ij}$ is the adjacency matrix element ...
-3
votes
0answers
51 views

Graph Theory: How to proof the Fan Lemma? [closed]

Fan Lemma: If $G$ is $k-connected$, then $G$ has a $(v, W)-fan$ with at least $k-paths$, whatever $v \in V$ and $W \subseteq V \; \backslash \{v\}$ with $\mid W \mid \ge k$.
1
vote
0answers
43 views

expected value of sum of weights in a random directed graph

Assuming we have a random directed weighted graph with $n$ nodes. Furthermore let us assume the nodes are divided into two categories: A node $i$ is of category C if there are only outgoing edges or ...
2
votes
0answers
35 views

Minimal vertex cover [closed]

For a vertex $u$ in a graph $G$, let $N_G(u) = \{v \in V (G)|\{u, v\} \in E(G)\}$. For $U \subseteq V(G)$, define $G\setminus U$ to be the induced subgraph of $G$ on the vertex set $V (G) \setminus U$....
0
votes
0answers
24 views

In a graph $G$, why can at most two vertices be adjacent to all of $E(G)$?

I'm going through a proof using this fact. I'm assuming the degree sum formula applies, but I still can't wrap my head around this fact.
3
votes
1answer
39 views

A random $r$-regular graph can be generated by taking union of a a random $(r-1)$-regular graph and a perfect matching.

$\newcommand{\lrp}[1]{\left(#1\right)}$ $\newcommand{\set}[1]{\{#1\}}$ $\newcommand{\mc}{\mathcal}$ $\newcommand{\E}{\mathbb E}$ $\newcommand{\N}{\mathbb N}$ Definition. Let $(\Omega_n, \mc F_n)$ be ...
0
votes
2answers
25 views

Are decision trees sparse or dense?

Are decision trees or game trees such as these sparse or dense? This wiki page goes on about calling trees "tight". Is that dense or a third type? Also if the graph is sparse, must its matrix ...
0
votes
1answer
157 views

If every subgraph of an undirected graph has at least one vertex with degree at most $k$, then the graph can be colored with at most $k+1$ colors.

I try to prove the following statement: "If every subgraph of an undirected graph has at least one vertex with degree at most $k$, then the graph can be colored with at most $k+1$ colors" My first ...