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

The Laplacian spectra of random graph $G(n,m)$ and $G(n,m+k)$

I am currently doing some work related to the eigenvalues of the Laplacian of a graph. Define $\sigma_i=\frac{\lambda_i}{\lambda_2}$, where $0=\lambda_1<\lambda_2\leq\cdots\leq \lambda_N$ is the ...
1
vote
0answers
44 views

Finding the longest path in a directed graph where each node can be visited $N$ times?

I've read that the longest path problem is $NP$-Hard, but what about where it is specified that each node can be visited a maximum of $N$ times? It seems the longest-path problem is a special case of ...
1
vote
0answers
33 views

Is class of graphs with eigenvalue $1$ of any particular importance?

Are graphs with eigenvalue $1$ of multiplicity more than $1$, important one? Please guide me to any book or article discussing such graphs.
1
vote
0answers
24 views

Small tree containing smaller trees

Given $n$, what is the smallest number $N=N(n)$ with the property that there exists a tree on $N$ (unlabelled) vertices that contains a copy of every tree on $n$ vertices? That such $N$ must exist is ...
1
vote
0answers
28 views

references of discrete association scheme

I tried to find a book or paper to understanding discrete association scheme but I could not get any book for that. What is the good references for that?
1
vote
0answers
63 views

Is it always possible to get MC/DC coverage on an $n$-input Boolean function with $n + 1$ test cases?

In software engineering, there is a coverage metric for testing called modified condition/decision coverage, or MC/DC for short. This metric is well-known in the avionics industry due to showing up in ...
1
vote
0answers
30 views

Show that any vertex $v$ of $P$ is half-integral.

Let $G$ be an undirected graph and define $$P=\{x \in R^{V}: x(u)+x(v) \leq 1 \:\:\text{for all edges}\:\: e=uv,\:\: x \geq 0\}$$ Show that any vertex $v$ of $P$ is half integral.
1
vote
0answers
23 views

Bipartite graphs whose minimal cycles have length $4$

Is there some literature about bipartite graphs whose minimal cycles all have length $4$? By that I mean that any cycle in the graph with length strictly greater than four can be divided into cycles ...
1
vote
0answers
37 views

Small graphs containing all trees on $n$ vertices

What do those graphs look like which contain a copy of every tree on $n$ vertices and such that no proper subgraph has this property?
1
vote
0answers
51 views

Graphs of (un)bounded color valence

Talking about colored graphs there is a definition given for graphs with bounded color valence. This definition is as follows: A vertex-colored graph $G=(V,E)$ has bounded color valence, if there ...
1
vote
0answers
21 views

Number of global min cuts in undirected graph

I'm looking at a proof of the following theorem "The number of global minimum cut is $\le \binom{n}{2}$". It says $\forall i$ from $1$ to $n-1$ Find min-cut seperating $\{1,2,\cdots,i\}$ from $i+1$. ...
1
vote
0answers
36 views

What is the probability of no cycles length $n$ in a simple, directed Erdos-Renyi graph with $n$ vertices?

What is the probability of having no cycles with length $n$ (touching all vertices) in a simple, directed Erdos-Renyi graph with $n$ vertices? For example, if $n=2$, then the probability is $1-P(...
1
vote
0answers
44 views

Non trivial results in graph theory/combinatorics coming from number theory

Are there any non-trivial results in graph theory that can be deduced from number theory or arithmetic geometry? I am not looking for expander graphs or applications however I am looking for ...
1
vote
0answers
58 views

Abstract dual of a graph and $K_{3,3}$

Let $G$ be a graph. The abstract dual of $G$ can be defined as a graph $G^*$ whose edges are in one to one correspondence with $G$ and whose spanning trees are obtained by taking the complements of ...
1
vote
0answers
44 views

Why graph factorization problems emphasize $k$-regular graphs

When we study graph factorization a lot of emphasis is placed on $k$-factorable graphs, i.e. graphs in which the factors are all $k$-regular. Why is such a factorization more important then say ...
1
vote
0answers
57 views

A directed graph and existence of vertex of finite degree

Let $\{1,...,k\}$ be a set of vertices of a directed graph, with no multiple edges. We say that paths $p$ and $f$ are disjoint by interior vertices if they are disjoint or have a common first or last ...
1
vote
0answers
27 views

Directed Graph $D$ has a Directed Path of At Least $\chi_u$ vertices

I've been working on some problems related to directed graphs in my computer science course, and I have been somewhat stumped on this one particular problem. Take a directed graph $D$, and consider ...
1
vote
0answers
36 views

Does the sweep line Algorithm produce a maximum independent set?

We know that a sweep line algorithm or plane sweep algorithm is a type of algorithm that uses a conceptual sweep line or sweep surface to solve various problems in Euclidean space [Wikipedia] Sweep ...
1
vote
0answers
27 views

Pseudo vertex-transitive graphs

I'm investigating finite, simple graphs with the following property: For each degree $d$ of $G$, the subgraph induced on all vertices of degree $d$ is vertex transitive. In particular, I'm ...
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
66 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
43 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
47 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
86 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
31 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
25 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
92 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
25 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
49 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
26 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
225 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 ...