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
1answer
293 views

Intersection and Union of sub graphs

can anyone phrase a common definition for the union and intersection for below case. Actually I am looking for mathematical expression in mathematical notations. For example if I want to do $G_1 ...
1
vote
0answers
10 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 ...
0
votes
0answers
12 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 path P ...
4
votes
0answers
26 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 , ...
12
votes
3answers
137 views

Game on simple finite graphs

Consider the following game on graphs (no multiple edges, but graphs can be disconnected). Players A and B alternate picking a vertex. After picking a vertex, a number is assigned to that vertex such ...
18
votes
11answers
9k views

Graph theory software?

Is there any software that for drawing graphs (edges and nodes) that gives detailed maths data such as degree of each node, density of the graph and that can help with shortest path problem and with ...
2
votes
2answers
127 views

Union of two matching sets being a matching

Let $G$ be a bipartite graph with parts $A$ and $B$. Let $U\subseteq A$ and $V\subseteq B$ and assume that there exists matching in $G$ that covers all vertices in $U$ and another matching that covers ...
1
vote
1answer
69 views

Extending matchings in a bipartite graph

Could I get some help for part b(i) of below please? Thanks. (Part (a) follows from Hall's Marriage Thm, and b(ii) follows quickly from b(i) I think). Let $G$ be a bipartite graph with parts $X$ and ...
1
vote
0answers
20 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$ ...
1
vote
2answers
55 views

Given $G = (V,E)$, a planar, connected graph with cycles, Prove: $|E| \leq \frac{s}{s-2}(|V|-2)$. $s$ is the length of smallest cycle

Given $G = (V,E)$, a planar, connected graph with cycles, where the smallest simple cycle is of length $s$. Prove: $|E| \leq \frac{s}{s-2}(|V|-2)$. The first thing I thought about was Euler's ...
5
votes
1answer
24 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 ...
1
vote
1answer
51 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$ ...
2
votes
2answers
977 views

Every $k$ vertices in an $k$ - connected graph are contained in a cycle.

Let $G$ be a $k$-connected graph. Meaning, $G$ has no less than $k$ vertices, and for every set of $k-1$ or less vertices, if we remove them from $G$, the graph stays connected (Of course, $G$ itself ...
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 ...
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?
0
votes
1answer
14 views

Prove that a directed tree does not have a path from a descendant to its parent

Prove: Let T = (V, E) be a directed tree. If v is a vertex of V and u is a descendant of v, then there is no path from u to v. My idea is that if u is a descendant of v, then there exist a path from ...
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
9 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
33 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 ...
1
vote
0answers
106 views

Average Degree of a Random Geometric Graph

A set of $N$ points are distributed randomly on a unit square with uniform distribution. Two points $\mathbf{p}_i$ and $\mathbf{p}_j$ are said to be connected if $\|\mathbf{p}_i - \mathbf{p}_j\| \leq ...
3
votes
0answers
44 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 ...
0
votes
2answers
2k views

Proving that a Euler Circuit has a even degree for every vertex

Theorem: Given a graph G has a Euler Circuit, then every vertex of G has a even degree Proof: We must show that for an arbitrary vertex v of G, v has a positive even degree. What does it ...
0
votes
1answer
33 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 $ ...
1
vote
3answers
121 views

How to calculate the number of automorphisms of a given graph?

How do determine the number of isomorphisms that a graph has to itself? For instance, suppose we have the following graph: How do I determine how many isomorphisms there are from G itself?
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 ...
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 ...
5
votes
1answer
302 views

Disjoint paths on grid graphs

Let $f(G)$ be the smallest $m$, such that one can find $2m$ vertices in $G$ with the following property: pair up the vertices in any way, and find $m$ paths that join each pair. Then every set of path ...
2
votes
1answer
48 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 ...
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 ...
5
votes
1answer
106 views

Euler, Grinberg,… who's next?

Given a cubic planar hamiltonian graph with $F$ faces. Let $a_k$ be the number of face of degree $k$ inside and $b_k$ outside the Hamilton cycle. We have the following: $\sum \limits_k ...
2
votes
2answers
161 views

Two disjoint spanning trees, spanning subgraph with all even degrees

Show that if a graph has two edge-disjoint spanning trees then it has a connected, spanning subgraph with all degrees even. I start by looking at the union of the two spanning trees. I know it has ...
0
votes
2answers
39 views

Partition of graph without cycles

Let $D$ be the maximum degree of $G=(V,E)$, and $k=\lfloor {D \over 2}\rfloor +1$, prove that there exists a partition of $V=V_1 \cup V_2 \cup...\cup V_k$ such that each $V_i$ spans a subgraph without ...
1
vote
3answers
124 views

Prove that for every planar graph, there is a partition $V = V_1 \cup V_2 \cup V_3$ such that the graphs with those are acyclic

Prove that for every planar graph $G = (V,E)$ with $|V| \geq 3$ there is a partition of V to $V = V_1 \cup V_2 \cup V_3$ such that $V_1 \cap V_2, V_1 \cap V_3, V_2 \cap V_3 = \emptyset$, where for ...
6
votes
1answer
117 views

A cycle of size at least $\frac{n}k$ in a graph with at least $3k$ vertices

My question is this: In a $G=(V,E)$ where $\alpha(G)\leq k$ (the maximum of the size of an independent subset of $G$) and $|V|=n\geq3k$, show that there is a cycle of size $\geq \frac{n}k$. Now, ...
5
votes
0answers
39 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 ...
1
vote
1answer
29 views

Is modularity of -1 possible

Wikipedia mentions that modularity of a network is within the range [-1,1).But if we consider a complete graph with n nodes and assign different community to each node than the modularity turns out to ...
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 ...
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. ...
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
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 ...
0
votes
2answers
297 views

Upper and lower bound on graph

Find upper and lower bound for the size of a maximum (largest) independent set of vertices in an n-vertex connected graph, then draw three 8-vertex graphs, one that achieves the lower bound, one that ...
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 ...
4
votes
2answers
89 views

Automorphism groups of vertex transitive graphs

Does there exist a finite nonoriented graph whose automorphism group is transitive but not generously transitive (that is, it is not true that each pair $(x,y)$ of vertices can be interchanged by some ...
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 ...
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
38 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 ...
1
vote
1answer
68 views

Existence of a trail of given length in a graph - NPC?

I am trying to determine, whether the problem of a trail of given length in a graph is a NPC problem. We have a graph $G = (V, E)$ and $k \in N^+$. Does this graph contain a trail of length at least ...