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

Determine the group of color preserving automorphism for the Caley color graph $D_∆ (Г)$ of following graph

Determine the group of color preserving automorphism for the Caley color graph $D_∆ (Г)$ of following graph My professor did this example in class and he got following group of color In order to ...
3
votes
1answer
38 views

Show that Peterson Graph has no 7 cycle

In order to prove that Peterson graph has no 7 cycle I read the proof given in http://people.math.sfu.ca/~goddyn/Courses/345shutdown/WestSolutions/solutions1.1.pdf The given proof is ...
2
votes
0answers
64 views

existence of a spanning subgraph with min degree $\delta$ and at most $(n-1)\delta$ edges

Question: G is a graph with n$\ge$2 vertices an min degree $\delta$. Prove that G contains a spanning sub graph of a min degree $\delta$ with at most $(n-1)\delta$ edges. Thoughts: For the induction ...
0
votes
0answers
36 views

Graph Algorithms

Can someone prove that the total number of partial trees of a given complete graph Kn, which doesn't contain a fixed edge e ∈ E(Kn) is (n-2)*n^(n-3), where n >= 3, n ∈ N.
1
vote
1answer
52 views

on the color classes of a $k$ chromatic graph

Let $G$ be a graph wich is $k$-chromatic. Suppose we have a coloring $(V_1, \ldots, V_l)$ such that each $V_i$ contains at least $2$ elements. I want to prove that $G$ has a $k$-coloring with this ...
0
votes
1answer
25 views

How many possible 2-colorings of a disconnected bigraph?

Is there a relationship between the number of connected components in a bigraph and the number of possible 2-colorings? A connected bigraph (i.e. only one component) can be 2-colored in exactly two ...
0
votes
1answer
23 views

Proof for k-connectedness of random graphs

I am really new to the theory of random graphs. It seems a lot of articles take for granted that: For $k\in\mathbb{N}\setminus\{0\}$ and $p\in(0,1)$ fixed, almost every graph in $G(n,p)$ is ...
1
vote
1answer
54 views

Number of $q$-colorings of an $n\times n$ grid graph without adjacencies

Suppose a square grid graph $g$ of side length $n$ can be colored with $q$ colors. In how many unique colorizations are no adjacent vertices the same color? A friend and I have been trying to find a ...
3
votes
5answers
194 views

Halting probability of random tree-generating algorithm

Suppose I have a tree-generating algorithm as follows. Begin with one root vertex. With equal probability, create either three subvertices or none. Recurse and repeat for each of the subvertices (if ...
0
votes
2answers
36 views

games in a round-robin tournament

How many games are played in a round-robin tournament held with n tennis players where each of the players will play against every other player exactly once. The answer is $\frac{n(n-1)}{2}$. What ...
0
votes
1answer
31 views

Bipartite Graph and Non-connected node?

Is this one bipartite graph or not? It is a simple question for you but i can't find the answer.
2
votes
1answer
69 views

Checking two graphs to be homeomorphic

How can I check that two simple connected graphs are homeomorphic? I know the defenition of homeomorfism, but I can't figure out when to stop subdividing, algoritmically. I need here some stopping ...
0
votes
0answers
29 views

Planar graph is bipartite iff its dual is Eulerian?

I know this theorem is true, but if the dual of the graph is not simple, i.e. a multigraph, how does that effect the result? Does this still work if the Eulerian graph is a multigraph and its ...
1
vote
1answer
5 views

Name for “Stratified” or “Synchronized” directed acyclic graph?

This may be a stupid question, but is there a name for a directed acyclic graph in which: every node can be organized into separate, sequential "bins" any two adjacent "bins" of nodes are a (not ...
0
votes
2answers
36 views

Proof. Theory graph. Please check.

If graph $G = (V,E) $ where $|V| = n $ is connectivity then $ n-1 \le |E| $ My proof: The our thesis is: $ \forall G $ is connectivity $\Rightarrow$ $ n-1 \le |E| $ I prove that using 'reductio ...
0
votes
1answer
45 views

Minimum and maximum number of edges graph with 25 vertices and 6 connected components can have

Let G be a simple graph with 25 vertices and 6 connected components. Find (i) the minimum number of edges that G can have. (ii) the maximum number of edges that G can have. What I know: The maximum ...
0
votes
0answers
11 views

Help understanding “How many connected graphs over V verticies and E edges” answer

I need to know the closed form for how many connected graphs there are with V vertices and E edges, so I found this: How many connected graphs over V vertices and E edges? Math StackExchange question. ...
0
votes
1answer
17 views

prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6

Question: prove that every graph with $n\ge7$ vertices and at least 5n-14 edges contains a sub graph with minimum degree at least 6. My proof: By induction. For n=7, the number of edges is 21=$2 ...
0
votes
2answers
23 views

Connecitivity graph. Easy task.

Let $G=(V,E) $ is a connectivity graph and $e\in E$ . Prove that $G'=(V, E - \{e\} ) $ is connectivity $\iff$ e is an edge $\in$ any cycle in $G$. Please help me with that.
0
votes
1answer
17 views

Why $f^{+}(v)-f^-(v) =val(f)$ if $v$ is the source?

I'm reading Bondy/Murthy's Graph Theory: He defines $x$ as the source and $y$ as the sink, reading a bit later in the chapter, he presents this definitions: $$ f^{+}(v)-f^-(v) = \left\{ ...
0
votes
2answers
27 views

Counting non-isomorphic graph.

How many exists non-isomorphic 4-regular graphs $G = (V,E)$ where $|V|=7$ vertices? I'm asking for hint to solve it with group theory( if it is possible) and without them
1
vote
1answer
24 views

Number of spanning trees for this graph

Find $\tau(G)$ for the graph $G$ below. This is what I tried so far: Let $e$ denote the horizontal edge between the two vertices as shown below. I wanted to use $\tau(G) = \tau(G-e) + \tau(G \circ ...
2
votes
2answers
35 views

Number of length-n paths in a graph with a fixed start vertex

So I was looking at a few past-years' papers from the ZIO (an IOI qualifier held here in India), and I found this question: I think this is the same as finding the number of paths of (let's take (a)) ...
3
votes
2answers
40 views

Proving a graph with $11$ vertices and $53$ edges is Hamiltonian

I have a graph with $11$ vertices and $53$ edges and I'm trying to prove it is Hamiltonian. I know that a graph is Hamiltonian if $n \geq 3$ and $d(v) \geq \frac{n}{2}$. I'm just having trouble ...
-1
votes
0answers
44 views

No perfect matching of k-regular graphs

For each $k\geq 2 $, find a $k$-regular graph that has no perfect matching. I found a link similar to this question but I am not familiar with the terminology, for example "$1$-factor". Is ...
-2
votes
1answer
133 views

Alternatively eliminating vertexes from graph

Anna and John play on a graph G, alternatively selecting distinct vertexes from it such that for each i > 0, v[i] is adjacent to v[i−1]. Loses the one who can't select anymore a vertex. Prove that if ...
-2
votes
1answer
31 views

Perfect matching of a tree

I wanted to prove that a tree $T$ has a perfect matching if and only if $T-v$ $(v \in V)$ has exactly one odd component for all $v$ which are vertices of the graph. (An odd component is a component ...
0
votes
0answers
14 views

k- regular graph matching [duplicate]

For each $k \geq 2$, find a $k$-regular graph that has no perfect matching. I found it true for $k=3, 4$ but don’t know how to write a generalised proof of it for all $k \geq 2$.
0
votes
1answer
35 views

Graph theory intro

For every graph G, prove that (vertex cover of G) is less than or equal to (twice it's matching). I tried a couple of examples and it works but I can't follow a trend to build my proof. Does anybody ...
1
vote
1answer
21 views

Partitioning a planar graph into spanning trees?

Suppose I have a simple, planar graph, which I want to partition into three edge sets such that each set forms a spanning tree. I've made an attempt at a solution, but it requires a few assumptions ...
1
vote
1answer
12 views

Describe the automorphism group of the digraphs

Describe the automorphism group of the digraphs Here is what I got so far For $D_1$, because of the direction of $vw$, we can't do anything to the graph so $Aut(D_1)= I$ For $D_2$, we can flip the ...
4
votes
1answer
17 views

Proving an equality in degree function in an undirected graph

Given an undirected graph $G=(V,E)$, and a permutation $\pi$ of the vertices, denote by $\Delta_\pi$ the $\max_{1\leq i\leq n-1} \{\deg_{\{v_{i+1},...,v_n\}}(v_i)\}$. That is, we look only on the ...
3
votes
1answer
32 views

NP completeness path problem.

We have the following decision problem. Let $G=(V,E)$ be a directed graph with edge weights $w:E \to \mathbb{R}_{+}$ and $B \in \mathbb{R}$. Is there a set $K$ consisting of directed vertex-disjoint ...
2
votes
1answer
23 views

Determine the number of distinct labeling of $K_{r,r}$

Determine the number of distinct labeling of $K_{r,r}$ In $G=K_{r,r}$, every vertices has degree $r$ so $|Aut(G)|=r$. I also know that the number of distinct labeling of $G$ of order $n$ is $\frac ...
2
votes
2answers
43 views

Why this graph has automorphism group is isomorphic to the cyclic group of order 4?

My professor say that this graph is a non-separable graph whose automorphism group is isomorphic to the cyclic group of order 4 without telling me why I can see this graph has no cut vertex, so ...
1
vote
1answer
36 views

Formulate the Marriage Problem into a Maximum-flow problem (Graph theory)

Suppose I have $M=\{1,\ldots, n\}$ men and $W = \{1, \ldots, n\}$ women and $B =\{1, \ldots, m\}$ brokers, such that each broker knows a subset of $M \times W$ and for each pair in this subset a ...
1
vote
0answers
29 views

are graphs/networks additive

I was wondering if networks/graphs are the sum of their parts. Let's say you have a 15-node network. The spectral density of that network has X kurtosis and Y skewness. You also have a 20-node ...
1
vote
1answer
36 views

Graph Theory into

Let M and N be matchings in a graph G with (cardinality of M) > (cardinality of N). Prove that there exists matchings M' and N' such that (Cardinality of M') = ((cardinality of M)-1), and (Cardinality ...
3
votes
1answer
36 views

Graph theory proofs

I am trying to prove that half of the vertex cover of graph is less than it's matching number. The problem is I don't know how to start and what the solution should be like, please help!
1
vote
1answer
103 views

A sequence of $n^2$ real numbers which contains no monotonic subsequence of more than $n$ terms

I'm following a Combinatorics course at the moment, and have recent proved the Erdős–Szekeres Theorem (or, at least, some variation of): A sequence of length $n^2 + 1$ either contains an ...
1
vote
0answers
31 views

Random Spanning Tree Edge Probability

I am working on a problem with a Loop Erased Random Walk used to create random spanning trees from a graph. The problem has many parts, but there are two hints to help with the more complicated ...
0
votes
1answer
17 views

Measure for presence of several poorly interconnected components in undirected graph

Is there a measure to classify networks regarding whether or not they are composed of several (internally closely connected) groups which are poorly connected (i.e. few links between groups). That ...
0
votes
1answer
6 views

Scale free networks (power law)

I'm working with a dataset, of which I'm analysing the degree distribution. I'm finding that it obeys the famous power law/scale free degree distribution $\propto k^{-\gamma}$, but the value of ...
0
votes
1answer
27 views

Is my idea of incoming/outgoing arcs correct?

I'm reading Jungnickel's Graphs, Networks and Algorithms. I've met the following lemma: I know that $e^{-}$ are the incoming vertices and $e^{+}$ are the outgoing vertices. Then I've tried to ...
1
vote
2answers
36 views

Whether the graphs G and G' given below are isomorphic

Whether the graphs G and G' given below are isomorphic?
4
votes
2answers
32 views

Graph contains triangle

Prove that if a simple graph of order n has more than n^2/4 edges then it contains a triangle. I know Martels theorem states the opposite condition for a triangle free graph but I'm not sure how to ...
0
votes
2answers
15 views

Node with loop graph completion

Is a graph consisting of a single node complete in addition to being simple? What about a node with a self loop:it's not simple but is it complete ?
1
vote
1answer
28 views

graph theory - clique graph

I am trying to understand the concept of clique graph. So I found this page. But I do not understand the example and what "graph intersection" is. Can somebody explain to me why $K_4$ is a clique ...
6
votes
0answers
77 views

Number of sets of vertices whose union of neighbours contains exactly $k$ vertices

Suppose a bipartite graph $g$ consisting of $2n(n-1),n\in\Bbb N,n>1$ vertices, is divided equally into two colors: red and blue, and is constructed as follows: For example, $g$ for $n=3$: If ...
0
votes
0answers
24 views

Lovasz number and bipartite complement

Let $G=(V,E)$ be a graph on $n$ vertices. An ordered set of n unit vectors $U=(ui|i∈V)⊂R^N$ is called an orthonormal representation of G in $R^N$, if $u_i$ and $u_j$ are orthogonal whenever vertices i ...