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

0
votes
0answers
10 views

In a bipartite graph $\alpha \beta \geq m$

That's basically it. $\alpha$ is the cardinality of the biggest independent set (no pair of vertices is connected) and $\beta$ is the cardinality of the smallest covering by vertices. I know this ...
0
votes
0answers
12 views

Construction of a Strongly Regular Graph which has regular subgraphs in all iteration.

Notation and Defination: $G$ is a Strongly Regular Graph( not a complete , cycle graph) with Every two adjacent vertices have $\lambda$ common neighbours. Every two non-adjacent vertices have ...
0
votes
0answers
31 views

Minimum Cake Cutting for a Party

You are organizing a party. However, the number of guests to attend your party can be anything from $a_1$, $a_2$, $\ldots$, $a_n$, where the $a_i$'s are positive integers. You want to be ...
0
votes
1answer
22 views

Longest path technique of proving a graph theory problem

Question: Let G be a simple graph, where the minimum degree of a vertex is k. Show that G contains a path of length at least k and a cycle of length at least k + 1. Proof: Consider the longest ...
4
votes
0answers
35 views

Average degree in graph

Let $G=(V,E)$. Assume for every $u,v \in V$ s.t. $(u,v) \notin E$ we have $deg(u)+dev(v) \geq 2k$ . Prove that the average degree is at least $k$. I tried looking at $G$'s complement , ...
1
vote
0answers
12 views

Hochbaum Pseudoflow (2012) - Highest Label DFS Variant

I got a very specific question concerning the paper "Simplifications and Speedups of the Pseudoflow Algorithm" - Hochbaum and Orlin(2012) I am afraid direct access to the paper is required to answer ...
1
vote
0answers
22 views

A question regarding matchings in bipartite graphs

Let $G=(V,E)$ be a graph with $V(G)=X\cup Y$, let $M_1$ be a matching that "covers" $X'\subseteq X$, and let $M_2$ be a matching that "covers" $Y'\subseteq Y$. Show that then there is a matching $M$ ...
5
votes
1answer
26 views

$n$-vertex $3$-edge-colored graphs with exactly $6$ automorphisms which preserve edge color classes, but permute the edge colors distinctly?

In each of these $3$-edge-colored graphs, there are exactly $6$ automorphisms which preserve the set of edge color classes: (These automorphisms don't necessarily map e.g. green edges to green ...
0
votes
0answers
10 views

Do hamiltonian paths exist on n-valent, simple, connected, planar graphs, where n>2?

I don't know to much about graph theory, so was wondering about the posted question. If it is too much perhaps you may know the answer if n is even? Any help is appreciated. Also, this is my first ...
0
votes
0answers
11 views

N-clique and n-clubs in the figure

I have a small doubt in this figure. What would be a 2-clique and 2-club in this figure? Is {1,2,3,4,5} a 2 - clique here? I am confused because if I take the sub graph, then 4 and 5 are 3 edges ...
0
votes
0answers
10 views

Regarding the Route Inspection Problem (Chinese Postman Problem)

The wikipedia article on the problem states that for a non-Eulerian graph, "the optimization problem is to find the fewest number of edges to add to the graph so that the resulting multigraph does ...
1
vote
1answer
40 views

Finding Automorphisms of Irregular graph through Regular Sub-Graphs.

Objective : To find a set of permutations for a irregular graph which is also a set of automorphism. This finding process uses permutations of 2 regular subgraphs of the given graph. Description and ...
3
votes
0answers
45 views

$G =(V,E)$ is $k$-connected ($k \geq 2$), prove that for every subset $S \subseteq V $, |S|=k there exists a cycle in $G$ that goes through all of $S$

I thought of starting from the Menger theorem which says that between every two vertices $u$ and $v$ there are $k$-edge disjoint graphs. So I think if I look at $G$ without the subset $S$ then I have ...
1
vote
1answer
52 views

Number of Automorphisms of a Irregular Graph.

I have been looking for results on number of graph automorphisms of irregular graph(upper and lower bound). I searched , but could not find anything which can be used directly. Say, $G$ is $k$ ...
1
vote
1answer
29 views

What is a transfer function?

If: $N$ is a set of nodes in a program dependence graph, which is a graph with two type of edge $L$ is a lattice of security levels What does the following mean: "For every $x\in N$, a so-called ...
0
votes
0answers
28 views

Every cycle is a composition of simple cycles

In a directed multigraph: Every cycle (closed walk) is a composition of simple cycles, right? Moreover, every finite path is a composition of simple paths, right? What is the simplest proof of ...
0
votes
1answer
34 views

$ G=(V,E_1 \cup E_2) $ is a triangle free graph, where $ G_1=(V,E_1) $ is planar and $ G_2 = (V, E_2)$ is a tree. Prove that: $ \chi (G) < 7 $

can anyone help with this, any direction could be helpfull? I've tried using the fact that $ G_1 $ satisfies that it's planar and is triangle free because G is. So we should have $|E_1| \leq 2|V|-4 $ ...
2
votes
1answer
53 views

Solution of Graph Isomorphism in current literature.

As of 2008, the best algorithm for graph isomorphism (Babai & Luks 1983) has run time $2^{O(\sqrt(n log n))}$ for graphs with n vertices. Does this algorithm gives a yes / no answer or provide ...
1
vote
2answers
24 views

Complete Toroidal Graphs

I've seen it referenced that $K_N$ is a toroidal graph for $N \leq 7$. Can anyone supply a proof (source link or outline) that $K_8$ is not a toroidal graph?
5
votes
0answers
40 views

Partition Of Graph's edges Into 3 Groups

Let $G = (V, E)$ be a bipartite graph. Prove that there is a partition of the set of edges $E$ into 3 disjoint parts: $E = E1 ∪ E2 ∪ E3$, $E1 ∩ E2 = E2 ∩ E3 = E3 ∩ E1 = ∅$, so that for ...
0
votes
0answers
14 views

G=(V,E) is a connected graph such that |V|=n, n>10 and the maximal degree is < 4. prove that there is a decomposition $ V=V_1 \uplus …\uplus V_k $

G=(V,E) is a connected graph such that |V|=n and the maximal degree is at most 3. Prove that you can decompose V into $ V=V_1 \uplus …\uplus V_k $ disjoint union of vertice set such that $ 10 ...
0
votes
1answer
18 views

A succinct proof that the given graphs (red $K_n$ drawn cyclically, plus blue $2$-paths between closest vertices) have dihedral automorphism groups?

Take the complete graph $K_n$ ($n \geq 3$), on the red-colored vertex set $\mathbb{Z}_n$, say, and add a blue-colored $2$-path between each pair of vertices $v$, and $v+1$, we get a sequence of graphs ...
3
votes
1answer
20 views

Graph Theory: How quickly will triadic closure create a complete graph?

Imagine we are given a graph $G$ comprised of nodes $N$ and edges $E$. Assume the graph is connected (i.e. there exists a path connecting any pair of nodes). We can then iteratively update this ...
5
votes
0answers
68 views

Maximum leaf number of an $m \times n$ grid graph?

Are there any results regarding the maximum leaf number of an $m \times n$ two-dimensional grid graph? Either a closed form, or a table of values for small $m$ and $n$?
0
votes
0answers
19 views

How to find connected components in a weighted graph using edge weight as a criterion? [on hold]

How to connected components in a weighted undirected graph using edge weight as a criterion factor? Please see the following two examples: Example 1 Example 2 I need the connected components whose ...
0
votes
0answers
16 views

Optimization problem shortest path distance and critical node detection problem (interdiction).

I am trying to formulate this optimization problem, max $d_{ij}$ where $d_{ij}$ is the shortest distance between active nodes i and j. However my problem is connecting my decision variable with the ...
5
votes
0answers
99 views
+50

If $G$ is shellable, then $G \backslash \{x_i\}$ is shellable?

A simplicial complex $\Delta$ on the vertex set $\{x_1,\dots,x_n\}$ is shellable if the facets of $\Delta$ can be ordered, say $F_ 1 , . . . , F _s$, such that for all $1 \leq i < j ...
2
votes
0answers
22 views

Cycle triplets: A beats B beats C beats A. Minimum and maximum number of triplets for round-robin tournament of $2n+1$ teams? (contest question)

From the 2006 Canada National Olympiad: Consider a round-robin tournament with $2n + 1$ teams, where each team plays each other team exactly once. We say that three teams $X, Y\text{ and }Z$, ...
2
votes
1answer
39 views

Mixed strategy problem - game theory

I have a basic doubt in a question of game theory. Assume that in a $2$ player game the mixed strategy profile $((a,b,0),(c,d,0))$ is a mixed strategy NE. Does the indifference condition in a mixed ...
0
votes
0answers
40 views

Maximum number of edges without perfect matching

Let $G=(V,E)$ where $|V| = 2n $ , I had to find the maximum number of edges in G , such that G won't have perfect matching. I found the answer ($(2n-1) \choose 2$, we can see it is tight by taking ...
3
votes
0answers
28 views

What is this graph theory measurement called?

I am reading a scientific paper that measures the "relatedness" $s_{AB}$ of two (not necessarily connected) subgraphs of a connected graph with the formula $$ s_{AB} = d_{AB} - \dfrac{d_{AA} + ...
0
votes
0answers
14 views

What does $M_{uv}^l$ represent?

Let $M$ be any non negative square matrix. What does $M_{uv}^l$ represent? $M_{uv}^l$: $uv$ entry of $M^l$. (When $A$ is adjacency matrix of a graph, then $A_{uv}^l$ is number of walks of length $l$ ...
0
votes
1answer
19 views

Representing all pairs shortest path in a graph with a matrix

Given a graph $G(n,E)$ where $n$ is the number of nodes and $E$ represents the edges. Is there a way to represent or transform this into a matrix containing all the shortest paths between two pairs ...
4
votes
3answers
67 views

Prove a graph $(V,E)$ with $d$-maximal degree let $k=d/2+1$ can be decomposed as $V=V_1 \cup\cdots \cup V_k$ where each $V_i$ is a loopless graph

I tried looking at a vertex v with the maximal degree, that is $d(v)=d$ and started looking at it's neighbours $$N(v):=\{u\mid (u,v) \in E\}$$ therefore $|N(v)|=d$, now between every two vertice ...
0
votes
0answers
29 views

Plotting Distance Constrained Points on a Plane

Does anybody know of some algorithmic way to tell if it is possible to plot a set of distance constrained points on a cartesian plane. Or, better still, a method to determine the minimum number of ...
2
votes
0answers
27 views

Eigenvalues of the product of two “incidence” matrices

I am trying to solve the following problem. Let the following incidence matrix of an undirected graph with four nodes $$ B = \begin{bmatrix}1 & 0 & -1 & 0 & 0 \\ -1 & 1 & 0 ...
3
votes
1answer
85 views

k! perfect matches

Let $G=($ $ A \cup B $ , $E$ $)$ be a bipartite graph with perfect matching. Denote $|A| = n$. Prove that if every vertex in A has degree $\geq$ $k$ then G has at least $k!$ perfect matches. ...
1
vote
1answer
49 views

Graph Isomorphism of Complete Graph.

what Is the complexity(computational complexity) of graph isomorphism of 1.Complete graphs($K_n$) and 2.Utility graphs (Complete bipartite graphs ,$K_{n,n}$)? is it in polynomial ? Looks ...
1
vote
1answer
44 views

A question about combinatorial commutative diagrams.

In the comments of this question the directed graphs that can appear as commutative diagrams are axiomatized: A graph is a combinatorial commutative diagram iff it's nonempty and such that any ...
0
votes
1answer
29 views

Shortest Path Length as mathematical function/expression

I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities. The degree of any node should be at least 3. The shortest path length ...
3
votes
1answer
81 views

Which directed graphs correspond to “algebraic” diagrams?

Any diagram for which the question of commutativity make sence is a directed graph, but not any directed graph make the question meaningful. $\require{AMScd}$ \begin{CD} A @>>> B @. A ...
0
votes
0answers
29 views

Application of Havel- Hakami Theorem [closed]

Definition :Given a sequence $d_1 \geq d_2 \geq \cdots \geq d_n$ called graphical if it is degree of a possible graph. need a proof of the question below. Question : The above sequence is graphical ...
2
votes
1answer
42 views

Finding a path in a graph by its hash value

Assume there is a graph $G = (V, E)$ and a hash function $H: V^n \rightarrow \{0,1\}^m$. Given a path $p = (v_1, v_2, ..., v_n)$ from the graph $G$, compute its hash value $H(p) = h_p$. Question: ...
-2
votes
0answers
33 views

combinatorial nullstellensatz [closed]

I was wondering if there is any trick for selecting the polynomial in Combinatorial Nullstellensatz method by Alon. This could be a powerful tool provided we choose right polynomial.
1
vote
0answers
80 views

Optimal allocation in network

We want to analyse specialization matters in a given network (N,g). Nodes represent individuals that can produce goods and services (just like in our usual economy) and that can be consumers too. ...
1
vote
0answers
23 views

Graph Theory: Find optimal subgraph that contains a certain node and a fixed number of nodes

I have a connected graph $G$ and a real-valued function $f$ on sub-graphs $G' \subseteq G$. Given a node $n \in G$ and a positive integer $s$, I am looking for the connected subgraph $G' \subseteq G$ ...
1
vote
0answers
81 views

How coefficients from finite field can form ring of polynomials?

Let us consider a graph $G(V,E),$ where $V$ is the set of nodes and $E$ is the set of edges. $\mathbf{x}=[X_1,\ldots,X_r]$ are symbols multicast by source to $|T|$ sink nodes. Symbols are from ...
2
votes
1answer
95 views

Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?

Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph. Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite. I know that $G$'s number of faces is ...
1
vote
0answers
45 views

what are these kind of graphs called in graph theory ?

Suppose the graph $G$ (here, we assume this graph is self-looped, i.e., each vertex is connected to itself) satisfies the following condition. For each vertex $v$ in $V(G)$, there is another vertex ...
1
vote
2answers
35 views

Find the total number of matchings in a complete graph with even vertices

I am trying to solve questions from a Walk through combinatorics.., I came across this proof which I was unable prove: Determine the number of perfect matchings for a graph with 2n vertices. I don't ...