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

Graph Example: Chromatic, clique, clique partition, and independence number

Find an original example of a graph whose chromatic number does not equal its clique number, yet whose clique partition number equals its independence number. I know what the chromatic, clique, and ...
0
votes
1answer
23 views

Can a graph be a subgraph if each component is not connected?

Say you two connected components of G. Can they be "combined" as one subgraph with no edges connecting them?
0
votes
0answers
24 views

NAUTY algorithm

NAUTY is a Graph Isomorphism(GI) software developed by Brendan McKay to test isomorphism of Graphs. It provides a practical solution to the Graph Isomorphism problem. It is a program for isomorphism ...
1
vote
1answer
12 views

Why is $0$ an eigen value of $L_G$?

I am learning Spectral Graph Theory. If the Laplacian Matrix of a graph $G=(V,E)$ is defined by $(a_{ij})=-1 ;(i,j)\in E, d_i ; i=j$ and $0$ otherwise then how does it follow that $0$ is an ...
0
votes
0answers
12 views

Prove that all linegraphs L(G) are claw free

For any graph G, prove that the line graph L(G) is claw-free. I have a fairly good intuition for this one but it's hard to put into words. I really need help with this one! I feel that I should use ...
1
vote
0answers
5 views

Number of cliques in a graph and intersection number

Define the number of cliques in a graph $G$ to be $c(G)$ and the intersection number of the graph to be $\omega(G)$. I have been tasked to comment on the inequality between $c(G)$ and $\omega(G)$. I ...
0
votes
1answer
11 views

Computing shortest path including specific edge

Consider the weighted undirected graph with $4$ vertices, where the weight of edge $\{i, j\}$ is given by the entry $W_{i, j}$ in the matrix $W$. $$W = \begin{bmatrix} 0&2&8&5\\ ...
1
vote
1answer
28 views

I don't understand how Kirchhoff's Theorem can be true

Kirchhoff's Matrix-Tree theorem states that the number of spanning trees of a graph G is equal to any cofactor of its Laplacian matrix. Wouldn't this imply that all cofactors of a Laplacian matrix ...
1
vote
0answers
31 views

Kuratowski's Theorem and Planar Graphs

Suppose there is a non-planar graph $G$ with $E$ edges and $V$ vertices, and that $G-e$ is planar for every edge $e$ of the graph. I am asked to show that $E-V=3$ or $E-V=5$. I know that I am supposed ...
0
votes
0answers
15 views

When is the complement of a connected graph also connected?

What are the conditions necessary for a graph and its complement to both be connected?
1
vote
0answers
30 views

How can I prove two empirically derived graphs are topologically equivalent?

I have two graphs that I've derived from an empirical data set and I suspect that they're topologically equivalent. It seems much easier to show that these graphs are not equivalent than to show that ...
0
votes
1answer
16 views

Independence Number Proof Explanation

In the following proof it states that "$v_i$ is less than or equal to the independence number for all $i$." Why is this true? I know what an independence number represents, I am struggling to ...
1
vote
0answers
21 views

Greedy algorithm fails to give chromatic number

Produce a graph and degree sequence for which the greedy algorithm fails to give the chromatic number. My first example is below- The first labeling uses 2 colors which is the chromatic number and ...
0
votes
0answers
13 views

A graph $G=(V,E)$ is connected and a vertex $s \in V$ is not a vertex separator iff $G-s$ is connected - requires $deg(s) > 3$?

I was asked to prove that $G$ is connected and $s$ is not a vertex separator iff $G-s$ is connected, given that $deg(s) > 3$. I'm struggling to understand why I need the $deg(s) > 3$ part. One ...
0
votes
0answers
8 views

incidence matrix of weighted directed graph

How is the incidence matrix of a weighted directed graph defined? By def, the incidence matrix $ M = (m_{ij}) $ is $n$ times $m$ matrix where $n$ is number of vertices and $m$ is number of edges. ...
3
votes
0answers
38 views

Is is possible that three countries have three points in common?

On the world map, there are several instances of three countries that have two points in common. For example, China, Russia and Mongolia. Is there any arrangement of three (fictional) countries such ...
1
vote
0answers
11 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 ...
0
votes
1answer
12 views

Proving statement for a tree-graph theory

So i need help with this: Let T be a tree. And degree of every vertice is an odd number. So i need to prove that there is an odd number of paths in that tree. So i basically need to prove that there ...
1
vote
1answer
40 views

Is there an hamiltonian path on a $4 \times 4$ chessboard

If you have a $4 \times 4$ chessboard: Is it possible to make a Hamiltonian graph such that each step is like a move of the knight? EDIT: But is an open knight tour? Thus possibly not an Hamiltonian ...
1
vote
1answer
23 views

Converting all arcs to polygonal arcs in a plane graph

I am trying to understand a proof on the conversion of arcs to polygonal arcs in plane graphs, in the book "Graphs on Surfaces" by Mohar and Thomassen. In the book, an arc joining two points $x,y \in ...
1
vote
1answer
18 views

Vertex deletion and chromatic number proof

Let G be a graph such that, for all vertices $a$ and $b$, $\chi(G-${$a-b$}$)=\chi(G)-2$. Prove that G is a complete graph. I started by drawing $K_5$ which has chromatic number $\chi(K_5)=5$ and ...
2
votes
1answer
34 views

Shortest Path Via Dynamic Programming Formulation?

We have a directed Graph $G=(V,E)$ with vertex set $V=\left\{ 1,2,...,n\right\}$. weight of each edge $(i,j)$ is shown with $w(i, j)$. if edge $(i,j)$ is not present, set $ w(i,j)= + \infty $. for ...
2
votes
1answer
21 views

How to get the directed line graph of the complete digraph?

When we replace every edge of the complete graph $K_N$ by a pair of directed edges, we get a complete directed graph, the Complete DiGraph $DK_N$ . Let $DL_{N}$ be directed line graph of the complete ...
0
votes
0answers
13 views

The Three Ways to Arrange Squares in Barnette Graphs

Below you see an example of a bicubic graph consisting of faces with degree $4$ and $6$, which makes up the set of graphs of my interest and is a subset of the so called Barnette graphs. ...
2
votes
1answer
46 views

How to draw that graph?

A specific set of graphs was given here: Let $G$ be a 3-regular connected planar graph with a planar embedding where each face has degree either 4 or 6 and each vertex is incident with exactly one ...
1
vote
1answer
25 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 ...
0
votes
1answer
25 views

example of a graph such that K(G)=δ(G)=Δ(G)E(G)

example of a graph such that K(G)=δ(G)=Δ(G), where K(G) is the number of components,δ(G) is the minimum degree of G and Δ(G) is the maximum degree in G.
0
votes
1answer
16 views

A finite, undirected, connected and simple graph with Eulerian circuit has $3$ vertices with the same degree

Let $G=(V,E)$ a finite, undirected, connected and simple graph, $|V| \ge 3. \space$ Prove: If $G$ has Eulerian circuit then $G$ has $3$ vertices with the same degree.
0
votes
0answers
11 views

Cuts in planar graphs

I am currently trying to prove the correspondence between cuts of a planar graph $G$ and the even sets of its dual, $G^*$. An even set $D\subseteq E$ is such that all vertices of $G^*$ are incident ...
3
votes
1answer
72 views

Number of faces in a planar graph bounded by odd length cycles?

Suppose that every face in a planar graph is bounded by odd length cycles, then the number of faces of this planar graph is even. I want to prove this using Euler's formula, but not really sure where ...
0
votes
1answer
32 views

What is the terminology for assigning $K_{m_i}$ (complete graph) to the $i$ th vertex, 'joining' if the corresponding vertices are adjacent?

Given a connected graph $G$ with $n$ vertices and given set of $\{m_1,m_2,...,m_n\}$ $n$ integers, we form a new graph $G^$ by considering the complete graph $K_{m_i}$ for each vertex i and 'join' ...
0
votes
2answers
26 views

Prove that if G contains an odd vertex then every vertex of G is odd

Let G be a graph with degree of each vertex either $m$ or $n$, where there are $m$ vertices of degree $m$ and $n$ vertices of degree $n$. Prove that if G contains an odd vertex then every vertex of G ...
0
votes
0answers
19 views

Probability of maximum degree in On random graphs I by Erdos

In The Maximum Degree of a Random Graph by RIORDAN et al., the authors commented that the study of the distribution of the maximum degree $d^{max}(G)$ of a random graph $G$ was started by Erdos and ...
0
votes
1answer
31 views

Confused with the power set of an integer

I am going through The Maximum Degree of a Random Graph by RIORDAN et al. On the second page, the notation $\mathbb{P}(\mathcal{D})$ is used which I assume the power set of the set $\mathcal{D}$. ...
0
votes
0answers
35 views

Here is a question on combinatorics [on hold]

here are ten items on sale at a bazaar, each costing less than one dollar. Prove that it is possible for two people to purchase distinct subsets of these objects and pay exactly the same amount. (Not ...
1
vote
1answer
46 views

Graph Theory Proof of Website Clicks [on hold]

Suppose we have n websites such that for every pair of websites $A$ and $B$, either $A$ has a link to $B$ or $B$ has a link to $A$. Prove or disprove that there exists a website that is reachable from ...
0
votes
1answer
31 views

Spectrum of k-partite graph

For a given undirected graph, it is known that the signless Laplacian $Q=D+W$ is positive semidefinite, where $W$ is the adjacency matrix and $D$ is the degree matrix. In particular, the smallest ...
0
votes
0answers
16 views

Matching as an induced subgraph

Let $G = (V, E)$ be a bipartite graph. Say $V'$ induces a $k$-matching if $G[V']$ has $2k$ vertices and $k$ edges such that every connected component contains two vertices. Does a graph $G$ wich ...
6
votes
0answers
27 views

Chromatic Number of Circulant Graph

Consider the Circulant Graph $Ci_{2n}(1,n-1,n)$ as described here: http://mathworld.wolfram.com/MusicalGraph.html Another way to describe $Ci_{2n}(1,n-1,n)$ would be $2n$ vertices with vertex set ...
0
votes
1answer
19 views

Prove that a graph is complete multipartite iff it has no $k_1 \bigcup k_2$ as a vertex-induced subgraph.

In graph theory, a part of mathematics, a $k$-partite graph is a graph whose vertices are or can be partitioned into $k$ different independent sets. A vertex-induced subgraph (sometimes simply called ...
0
votes
0answers
15 views

Determining intersection number of $C_n+C_n$ and $\overline{C_n}$.

Is there a method to compute intersection numbers of graphs? For example, I would like to compute the intersection number of $C_n+C_n$ and $\overline{C_n}$, where $C_n$ is the $n-$cycle. I was trying ...
0
votes
0answers
21 views

What is the probability of interpolating the Tutte polynomial of a planar graph from the values at the two hyperbolas?

Crossposted from MO The Tutte polynomial is a bivariate polynomial with positive integer coefficient which is a graph invariant and can be defined recursively. Evaluating it is $\#P$-complete even ...
2
votes
0answers
27 views

How to read Spectral Theory of Graphs

My background is a course is Linear Algebra -Hoffman,Kunze Graph Theory-Clark. I am reading Spectral Theory of Graphs. My professor has asked me to start from the book Spectra of Graphs by ...
0
votes
0answers
32 views

To show the Petersen graph has $2000$ spanning trees. [on hold]

I want to show that the Petersen graph has $2000$ spanning trees. How can I achieve it?
1
vote
0answers
10 views

Eigenvalue ratio evolution of Laplacian matrix when add edges

Consider an connected digraph, we use the classic definition of the Laplacian matrix $L$: $L=D-A$, where $D$ is the degree matrix and $A$ is the adjacency matrix. There has been many researches on ...
0
votes
0answers
15 views

An efficient algorithm to decide if a directed graph is unilaterally connected

I have been doing practise problems in designing algorithms and came across the following in a past test from an American university (see attached): A directed graph is unilaterally connected if, ...
0
votes
0answers
4 views

Counting subgraphs of bounded extremal degrees

Let $m\leq n-1$. Is there a closed expression counting the subgraphs of minimum degree $\geq m$ (resp. maximum degree $\geq m$) on $n$ labelled vertices?
1
vote
0answers
31 views

Use Gröbner bases to count the $3$-edge colorings of planar cubic graphs…

I found a nice introduction on how to Use Gröbner bases to construct the colorings of a finite graph. Now my graphs $G=(V,E)$ are the line graphs planar cubic graphs, so they are $4$-regular. The ...
0
votes
0answers
8 views

Decomposing a graph into $N$ planar sub-graphs that can be drawn on $N$ planes.

I would like to ask you if there is a way for checking if we can decompose a specific graph into $N$ planar sub-graphs that can be drawn on $N$ planes without an edge crossing any of the planes.
2
votes
0answers
18 views

Are there useful visual representations of magmas?

In group theory we have Cayley graphs. Are there analogous or anyway useful visual representations of magma structures? I am unsure about how to construct a graph representing, for instance, a free ...