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

How can you find the total number of non-isomorphic unlabeled graphs with n vertices?

I have seen some questions about labeled graphs, but no answers for an unlabeled graph. I calculated for the first four graphs and it seems to be $2n-1$ total graphs for $n$ vertices. I'm not sure if ...
0
votes
2answers
29 views

Edge that does not appear in ANY spanning tree?

I have a problem that just puzzles me... I am told I have a graph $G$ and asked what I can say about an edge that appears in no spanning tree of $G$. My question is...is there such an edge to start ...
1
vote
2answers
24 views

Euler Formula for planar graphs

Sorry to post questions so many times...but I'm confused with what use Euler's formula for planar graphs has. Because, say, $K_4$ the complete graph with 4 vertices is planar after some rearranging ...
1
vote
1answer
26 views

Closed form of S(n):

The following problem is about a game played with wooden blocks stacked vertically. The way the game is played is as so: There is a stack of n blocks available on a table in front of you; With ...
0
votes
1answer
20 views

Oriented graph VS directed graph?

Alright, while the definitions are stated in my lecurenotes, textbooks and wiki, I'll be honest, it just explodes my mind with what seems like word sorcery. Definition: A directed graph is called an ...
2
votes
1answer
14 views

Proof of the need of an even degree for a graph to be factorizable

For a graph to be factorizable, it seems it has to be of even degree. Could anyone give a simple proof thereof? Thanks in advance.
1
vote
1answer
28 views

Induced subgraph with radius rad(G)-1

Let $G$ be a simple connected graph with $rad(G)=r$. From all the induced subgraphs of $G$ with radius $r$ let $H$ be this with the least number of vertices. I want to show that for every vertex that ...
2
votes
2answers
50 views

Relation between rad(G) , Δ(G) and |G| in a graph

Is there a formula for resolving the following question : "Given a graph G with rad(G) = 3 and Δ(G) = 5, can we have |G| = 2006?" rad(G) is is the minimum graph eccentricity of any vertex in G.(The ...
2
votes
1answer
35 views

Check existence of walk visiting every node in graph odd-times

Lets have an undirected connected graph G(N,E) and pair of colors {C1,C2} Assign every node the color ...
1
vote
2answers
62 views

I found a Graph that defies the answer to this question…

I have this problem from graph theory which I am not entirely convinced with... I am asked if there is a graph with six vertices with degrees {2,2,2,4,5,5}. Answer, is apparently NO. My question ...
-2
votes
0answers
20 views

Deducing number of vertices in a tree given degrees of vertices [closed]

A certain tree has two vertices of degree 4, one vertex of degree 3 and one vertex of degree 2. If the other vertices have degree 1, how many vertices are there in the graph?
0
votes
0answers
14 views

Expected size of largest connected component in a binary matrix

Let $C_4(\mathbf M)$ and $C_8(\mathbf M)$ denote the size of binary matrix $\mathbf M$'s largest 4-connected component and 8-connected component of the same value, respectively. For example, the ...
0
votes
1answer
29 views

Extracting l(G) edges from an l(G) edge connected graph with diameter 2.

Let $G$ be a simple connected graph with $diam(G)=2$ and $S\subset E(G)$ with l(G) edges where $l(G)$ is the edge connectivity of the graph such that $G-S$ is not connected. I want to show that at ...
6
votes
0answers
107 views
+300

graph product that commutes with automorphism, and semi direct

Is there a way to construct a "product" of graphs $G\rtimes H$ such that $Aut(G \rtimes H ) \simeq Aut(G) \rtimes Aut(H) $? A related topic is "Semidirect product" of graphs? but not quite ...
2
votes
2answers
53 views

Why the Petersen graph is edge transitive

It is everywhere, but I cannot see it from scratch. For example the graph $K_{1,3}$ given here (p23), it is easy to see why it is edge-transitive and not vertex-transitive. The definition given in ...
0
votes
0answers
18 views

Parallel Algorithm for Donor/Recipient Matching - Graph Matching/Optimization [closed]

This question was cross-posted and answered on Computer Science Stack Exchange. I'm not certain I can accurately describe the problem using my knowledge of discrete math, so pardon any ...
1
vote
0answers
36 views

Directed Graph Equivalence Class

Consider the following conversion involving directed graphs. To convert from $\mathcal{G}$ to $\mathcal{G}^u$ (they have the same number of vertices): $V_i \rightarrow V_j$ in $\mathcal{G}^u$ iff ...
0
votes
0answers
17 views

Can matrix generated by ith power of adjacency matrix, have -ve value?

I read that - The uv-entry of the k-th power $$A^k$$ counts the number of walks of length k from the vertex u to the vertex v. I wanted to know if such a matrix can have negative values, and ...
1
vote
1answer
29 views

Matching with number of edges from one side

Let $A=\{a_1,\ldots,a_k\}$ and $B=\{b_1,\ldots,b_l\}$ be two sets of students. Suppose that each $b_i\in B$ knows at least $m$ students in $A$. Can we always find $m$ disjoint pairs $(a_i,b_i)$ such ...
3
votes
2answers
146 views

Showing planarity of graphs

I am trying to show $G_3$ is planar. I have constructed $G'_3$ as shown. Is it correct to say that by the Jordan curve theorem, $G_3$ cannot be planar, as any drawing will cause edges to overlap. ...
0
votes
0answers
22 views

let G be a connected regular graph that is not eulerian [closed]

I am facing a lot of difficulty about that problem which i post. so please send me a solution of that problem. I know about the basics of elurian graph but do not have grip of that topic.
2
votes
2answers
79 views

What are some applications of loops in real life? [closed]

I am aware of the real world applications of simple graphs and graphs with multiple edges but how are loops used? For example, a few computers linked to each other would be an example of simple graphs ...
1
vote
2answers
30 views

Properties of regular bipartite graphs

I am often asked to prove properties of regular bipartite graphs, and beyond the two parts having equal size nothing seems obvious. Are these graphs more intuitive than they first seem? In ...
1
vote
1answer
24 views

Decide if this cubic graph on 8 vertices is planar

Because I couldn't count faces and carry out Euler's formula for planar graphs I decided to "find" the $K_{3,3}$ subgraph in this way I'm not sure is how we're supposed to do it. Given this graph ...
0
votes
1answer
16 views

Can a chord determine two fundamental circuits in a graph

I was studying fundamental circuits,fundamental cutsets related theorems,then I came across a question in my mind: Is it possible that a chord with respect to a given spanning tree in a graph ...
1
vote
1answer
28 views

spectrum of complete p-partite graphs

I need to determine the spectrum of the complete p-partite graph ( in which each partite set has m vertices) using the complement. How can i show this? I know the spectrum of the adjacency matrix of ...
0
votes
1answer
22 views

Every graph of degree 2 is planar

A graph is planar if it can be drawn on flat paper so that no lines cross each other. Suppose G is a component where every node has degree 2, and no node in G has arc to itself. Is G ...
1
vote
1answer
22 views

Among the various subgraphs of $K_5$, how many are cycles?

Among the various subgraphs of $K_5$, how many are cycles? I know the answer is $37$ because the number of $3$-cycles is $10$, the number of $4$-cycles is $15$, and $5$-cycles is $12$. Could anyone ...
-1
votes
1answer
54 views

Mathematical Induction - Graph Theory

Prove by induction on $n$ that $K_n$ (the complete graph on n vertices) has a Hamiltonian cycle for all $n \geq 3$. I understand this can be done not using induction, however I am very new to ...
0
votes
1answer
83 views

Density of Subgraphs

I am stuck trying to make sense of this review problem: Given a graph G(V, E), we say that the induced subgraph G(S) on a subset of vertices S ⊆ V is a subgraph of G whose vertex set is S and edge ...
1
vote
1answer
72 views

Proving that if $G$ has a Hamiltonian circuit, then the line graph $L(G)$ also has a Hamiltonian Circuit

I have a graph G = (V, E). I know that the line graph L(G) of G is defined as follows: each vertex in L(G) corresponds to an edge in G, and two vertices are connected by an edge in L(G) if and only if ...
2
votes
0answers
32 views

Logic to identify the “minimal paths” in a directed (ordered) acyclic graph (DAG)

I am a reliability engineer and nowadays trying to write a code which analyse complex reliability block diagrams (RBD). (my profession is industrial eng.) RBD properties (valid always): directed ...
-1
votes
0answers
21 views

coloring a graph in which every two cycle have at least a common node

consider a graph, in which every two cycle have at least one common node. prove that it can be colored with 5 colors. (I think its called the chromatic number.)
1
vote
0answers
18 views

Interpretations of a weighted adjacency matrix's eigenvectors and eigenvalues?

Suppose that I have weighted undirected graph $G$, and the corresponding adjacency matrix which is a symmetric matrix $A$. Suppose that the edge between node $i$ and $j$ has weight $w_{ij}$, then $$ ...
2
votes
0answers
19 views

Find ordering of directed weighted graph maximizing sum of edges 'going up'

Consider the following problem. Given a weighted directed graph $G=(V,E)$ with $n = |V|$, find an ordering $\pi: \{1,...n\} \to V$ of the vertices that maximizes $$ \sum_{i<j} w_{\pi(i),\pi(j)}. $$ ...
1
vote
0answers
14 views

Scale-free property of random graphs

From this Wikipedia page, I gather that when the degree distribution of a graph obeys the power law, the graph is termed 'scale-free'. I would like to know the reason for this term. What has scaling ...
2
votes
1answer
58 views

Between any two vertices $u,v$ in a 3-connected graph, there are two internally disjoint $u$-$v$ paths of different lengths?

I am trying to solve the following exercise about 3-connected graphs from this book. (a) Show that for every two vertices $u$ and $v$ of a $3$-connected graph $G$, there exist two internally ...
1
vote
1answer
43 views

Are $G_1$ and $G_2$ isomorphic?

If $G_1$ and $G_2$ are two regular graphs on same no. of vertices,with same regularity and have identical Laplacian spectrum, are $G_1$ and $G_2$ isomorphic?
0
votes
0answers
6 views

proving properties of (graph) dominance defined via a system of equations

Some notions on graphs can be defined via a system of equations with values in a lattice. For example, dominance $d(v_1, v_0)$ ($v_1$ dominates $v_0$) in a graph $g$ is defined by a system $\forall ...
1
vote
1answer
52 views

Existence of infinite subsequence of trees with a special condition

For rooted trees, define $children(v)$ as the number of children of the vertex $v$. Assume two operations on rooted trees: contract an edge: choose an edge $E$, join two vertices adjacent to $E$ ...
1
vote
1answer
20 views

Finding $k$-clique in a graph with running time of $|V|^{k-1}$

This is a homework problem. Let's say I have a graph $G$, how can I find a $k$-clique (i.e. a complete graph with $k$ vertices) inside $G$? So far I can think of a naive solution where I check if each ...
3
votes
2answers
80 views

Finding all k-size subgraphs

I have no experience with advanced combinatorics, but I have to solve a problem that I think I will need advanced combinatorial techniques, correct me if I am wrong. Let $G$ be a large directioned ...
2
votes
0answers
50 views

Assignment problem with multiple types, capacities and costs

I am trying to solve an optimization problem (variation of assignment problem). I'm stuck with how to represent this problem (as an LP or graph based). If it's formulated as a LP, I'm unsure of how to ...
1
vote
1answer
41 views

Number of orbits in a graph.

I am confused with this concept. Consider for instance the graph $G$ with $V=\{v_1,\dots, v_{10} \}$, $E=\{12, 15, 16, 23, 27, 34, 38, 45, 49, 67, 78, 89, 910, 510, 610 \}$. This is a 3-regular ...
2
votes
0answers
19 views

Is there a simple relationship between the eigenvalues of a graph and a transition matrix?

Let $A$ be a adjacency matrix defining a graph, in which $A_{ij}=1$ if there is an edge between $i$ and $j$ and $A_{ij}=0$ otherwise. Let $P_{ij}=\frac{A_{ij}}{k_i}$ in which $k_i=\text{sum of ...
1
vote
2answers
47 views

Minimum size of largest Clique in a Graph

I am trying to solve a programming challenge involving cliques, but am having a hard time wrapping my head around the mathematics behind the theory. https://www.hackerrank.com/challenges/clique ... ...
1
vote
2answers
31 views

Writing basic proofs about cycles?

These are extremely straightforward statements, but I'm getting flustered by how someone would go about constructing proofs to solve these... (a) Every cycle is connected (b) Every cycle is ...
0
votes
0answers
12 views

Edge-partition graph into maximum distinctive paths

Is anyone aware of a graph partitioning algorithm in which each partition is a path and where the criteria for partitioning is to maximise the difference between partitions where two paths are ...
0
votes
1answer
23 views

Proof that there is at most one perfect matching in a tree

I'm trying to understand this proof to prove that there is at most one perfect matching in a tree. Let M, M' be perfect matchings in the tree T = (V, E) and consider the graph on V with edge set ...
0
votes
3answers
21 views

Prove that for any graph G the number of vertices multiplied by the lowest degree is $\le$ the number of edges multiplied by 2

For this proof. I know that number edges is half the sum of the degree sequence since vertices are connected only once. So if the edges are doubled that means, it will definitely be more than the ...