Questions tagged [graph-theory]

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.

21,460 questions
Filter by
Sorted by
Tagged with
13 views

All connected graphs without the induced copy of the path

Following this questions, I am interested in determining all connected graphs with the property that they do not contain an induced copy of the path on two edges. I did all I could but no avail. ...
24 views

Determine all $n$-vertex simple graphs $G$ such that every induced subgraph of $G$ with $3$ vertices has either $1$ or $2$ edges.

I got an interesting question in graph theory: Let $n \ge 5$. Determine all $n$-vertex simple graphs $G$ such that every induced subgraph of $G$ with $3$ vertices has either $1$ or $2$ edges. One ...
43 views

How to describe the graph of wedding guests mathematically?

I'm working with a particular graph problem and I'm not sure how to describe it. I dug up my algorithms textbook and can't find anything exactly right. I'm trying to plot a path through a weighted ...
31 views

Prove there is an odd-sized cycle with every edge of a different color in a $n$-vertex multigraph

Consider an $n$-vertex multigraph. Every edge is coloured by one of $n$ colours and the edges of each colour form a cycle of odd length. Prove that there is a cycle of odd length whose edges are all ...
38 views

If an undirected graph consists of a cycle, then what is the starting point of the cycle?

I was recently trying to code up the following problem : Given an undirected graph G = (V,E) design an algorithm to check if the graph consists of a cycle or not. The problem is fairly simple and one ...
30 views

Graph Eulerian-Hamiltonian.

Among 9 children, every child knows at least 4 children. Can these children be arranged in a line so that every child know the child beside him? This question is part of a Practice in my college under ...
42 views

Prove that described graph contains $K_{2, t}$ as spanning subgraph

Let us consider graph $G$ that doesn't have multi edges and loops. Let it satisfy following inequality $$\sum_{x\in V(G)} \binom{\deg(x)}{2} \ge (t - 1) \cdot \binom{n}{2} + 1$$ then prove that $G$ ...
23 views

24 views

Simple graph with vertex degree $\geq k$ has a matching of cardinality $\min\{k,\lfloor \frac{|V|}{2}\rfloor\}$

Essentially, I'm referring to this question The part I don't understand is why a graph with $|V|<2k$ must have a matching of cardinality $\lfloor \frac{|V|}{2}\rfloor$. Can someone explain? The ...
80 views

Maximum number of edges in a balanced graph with n points, without small cycles (say, of length 2, 3, 4)

Let's say we have $n$ points numbered from $1$ to $n$. What is the maximum number of directed edges possible on a graph with these $n$ points: without any cycle of length $\leq k$, for example ...
31 views

Induced edver-free graphs

A graph of order $3$ in which there is exactly one edge we will call edver (edge + vertex). It is quite easy to prove the following statement. For a finite simple graph $G$ the following statements ...
16 views

31 views

Petersen's automorphism group

I want to find the automorphism group of Petersen. But I don't know if I'm counting all of them or not. If we assume that the vertices of the graph are labeled as $1,2,3,4,5$ (Because I think we only ...
44 views

Why is the universal covering tree of $G$ unique up to isomorphism and how to obtain the covers of $G$ of quotients thereof?

Let us start from defining the universal covering tree of a graph $G$ to be the infinite tree $\mathcal{T}$ such that any cover $H$ of $G$ is a quotient of $\mathcal{T}$. It is well known that the ...
46 views

Is there a graph with 2-factor that is not hamiltonian?

If a graph $G$ has a 2-factor it means it is a 2-regular subgraph that contains all vertices of $G$. Isn't it a hamiltonian cycle? because it is 2-regular so it is a cycle and it contains all vertices ...
31 views

Chromatic polynomial of harmonious coloring

has anyone encounter a chromatic polynomial of a harmonious coloring? The assumption I made is that since the harmonious graph looks like a tree, then the chromatic polynomial of a tree can be used to ...
69 views

Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex of $G$ lies on a cycle of length $27$

Prove that if $G$ is a graph of order $101$ and $δ(G) = 51$, then every vertex of $G$ lies on a cycle of length $27$ (Chapter 3 Exercise 16.a Chromatic Graph Theory,Gary Chartrand, Ping Zhang) ...
153 views

Minimal set definition

I'm very confused about minimal sets, particularly with graphs. According to Wolfram Mathworld, a minimal set is "a member set that is not a proper subset of another member set is called a ...
469 views

Are all isomorphisms between the Fano plane and its dual of order two?

Famously from every finite projective plane $P$ we can create a dual projective plane $P'$ by taking the points of $P'$ to be the lines of $P$ and the lines of $P'$ to be the points of $P$. It is also ...
22 views

Are there many approximation algorithms that solve the problem of "job scheduling with conflicts on parallel machines"?

First, sorry if this is not the proper type of question for this stack exchange. I need to collect scientific sources/papers about job scheduling with conflicts on parallel machines. This is a problem ...
34 views

16 views

Form of the smallest vertex cover in a bipartite graph

I'm trying to write a proof of Konig's theorem using Menger's theorem. However, I got stuck along the way. In order to move forward I'd (apparently) need to show the following fact. Let $G$ be a ...
29 views

What does it mean for a graph to be $P_3$-free (or more generally $P_k$-free)?

I'm confused on this. Does it mean that there is no induced subgraph that is $P_3$? Does it mean that any set of 3 connected vertices must be a triangle? Or, for $P_4$, a square? Pictures would be ...
28 views

To find the number of regions of $G_{k-1}$ in a chain of planar graphs.

Consider a connected simple planar graph $G$ and a chain of subgraphs $G_1,G_2,\dots,G_k=G$ of $G$, where each subgraph $G_j$ has $j$ edges and where $G_{j-1}$ by adding $1$ edge and at most $1$ ...
39 views

Teletrasporation step in Page Rank

I'm reading some definition of page rank, in particular how page rank work on the web graph. I'm a little bit confused about the definition of the teletransportation step. How I understand this phase ...
8 views

Prove that in a Weighted Cycle Graph there's an edge not used by all paths that go through a maximal edge

Given a weighted cycle graph $C_n$ and some maximal edge $e_{max}$ in the case that some minimal paths between two vertices go through $e_{max}$ prove that there exists an edge that is not part of any ...
Is a uniformly random $r$-regular bipartite graph $r$-edge connected with high probability?
A graph is $r$-edge connected if the number of edges in a minimum cut is at least $r$. It is known that a random $r$-regular graph is $r$- vertex connected (which implies $r$-edge connected) with high ...