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.

Filter by
Sorted by
Tagged with
1
vote
1answer
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. ...
0
votes
1answer
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 ...
0
votes
1answer
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 ...
3
votes
0answers
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 ...
0
votes
0answers
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 ...
1
vote
0answers
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 ...
1
vote
2answers
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$ ...
0
votes
0answers
23 views

Define a directed edge in a DAG using partial ordering

I am trying to describe a novel type of DAG's construction algorithm (in computer science). The directed edges of the graph correspond to a partial ordering: i.e. any directed edge $e$ spanning from $...
0
votes
1answer
36 views

Upperbound for difference between chromatic number $\chi(G)$ and list-chromatic number $\chi_L(G)$

As we all know, coloring is just special case of more general thing, list-coloring. And it leads to conclusion that $$\chi_L(G) \ge \chi(G)$$ Well, it is pretty cool, but is there any upperbound on ...
1
vote
1answer
58 views

Erdos (1970) proof of Turan's Theorem - Applying induction on S

I am following "Turan's Graph Theorem" by M. Aigner. In the second proof by Erdos, he states, "Applying induction on S, we thus infer that among the graphs with a maximal number of ...
2
votes
1answer
24 views

Characteristic vector of independent points in a graph

I'm trying to understand vertex packing polytopes, and have run into some definitions that I don't understand properly. In the summary of this paper, the authors say that the vertex packing polytope ...
0
votes
1answer
46 views

What are the chromatic polynomial of these graphs?

What are the chromatic polynomial of these graphs? I first add the edge fk, and Then I contract this edge and then use the following theorem $P(G)=P(G^{+}_{e})+P(G^{++}_{e})$, where e is the edge fk....
1
vote
0answers
21 views

Algorithm for computing joint probability distribution from conditional probability table using tensor multiplication in Bayesian Network?

I get stuck on this problem. If in a Bayesian network, how can we do tensor multiplication on the conditional probability table so that it eventually gives the joint probability distribution? If a ...
0
votes
0answers
23 views

Is there a relation between Hall's Theorem and the Gale-Shapley Deferred Acceptance Algorithm? If so, what?

Is there a relation between Hall's Theorem and the Gale-Shapley Deferred Acceptance Algorithm or the Rural Hospitals Theorem? If so, what? If not, why not?
3
votes
1answer
34 views

Is there a graph without a $K_5$ subdivision that has a chromatic number of $5$?

The Four Color Theorem states that a planar graph requires at most four colors to be proper colored. The Kuratowski's Theorem states that a graph is planar if, and only if, it doesn't have a subgraph ...
5
votes
0answers
88 views

Encoding information by hiding digits

Good evening, I have been stumbled by this problem. Two magicians, call them A and B, play a trick: while B is not looking, A asks a spectator to write an n-digit number on a board. A then cancels two ...
4
votes
1answer
43 views

Every graph $G$ contains a subgraph $H$ such that $\deg_H(v) \geq \chi(g) -1$ for every vertex

I stumbled upon following theorem for which no proof was given: Let $G$ be an undirected and simple graph. Then there is a subgraph $H$ of $G$ such that $\deg _H (v) \geq \chi(G) - 1$ for every ...
0
votes
0answers
17 views

Minimum possible largest biconnected component in a graph [closed]

Let $|V|$ be the number of vertices in a graph and $|E|$ be the number of edges. All graphs has a decomposition into biconnected components. For a given graph $G = (V,E)$, we define $C$ as the number ...
0
votes
0answers
28 views

Graph Representation for Boolean functions

I'm trying to classify a certain family of Boolean functions, and need to represent the function as a graph. Is there any well-known graph representation for a Boolean function that captures the ...
1
vote
1answer
30 views

If G is n regular, then G has n disjoint perfect matchings.

Let G be a bipartite simple graph show that: If G is n regular, then G has n paarwise disjoint perfect matchings. It's firstly easy to show that G has a perfect matching by using Hall’s Theorem, $|N(...
0
votes
1answer
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 ...
1
vote
1answer
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 ...
1
vote
0answers
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 ...
1
vote
0answers
16 views

Mobius Inversion Theorem that is used in Chromatic Polynomial

I have made a shortcut on proving the Mobius Inversion Theorem, which states the following: Let $N_{e}(x)$ to be a real-valued function, defined for all $x$ in a locally finite partially ordered set $(...
-2
votes
0answers
40 views

Prove that every graph $G$ with $n$ vertices and chromatic number $k=χ(G)$ has at most $\frac{1}{2} (n^2- \frac{n^2}{k}) $ edges. [closed]

Prove that every graph $G$ with $n$ vertices and chromatic number $k=χ(G)$ has at most $$\frac{1}{2} \left(n^2- \frac{n^2}{k}\right) $$ edges.
0
votes
0answers
23 views

Irreducible $\iff$ $G$ is strongly connected.

I have a question about a theorem relating reducible matrices with strongly connected graphs. In my book, there is the following definition: Definition Given $A \in \mathbb{R}^ {n,n}$, its associated ...
3
votes
1answer
73 views

Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph

Let $T$ be a tournament directed graph (round robin). Prove that there is an odd number of Hamiltonian paths in the graph. I am aware that this question may be considered a duplicate of this one: The ...
0
votes
0answers
20 views

How to solve min cost flow for indivisible items?

I have a transshipment problem of assigning supply to demand. Supply comes from multiple suppliers with different capacities. Demand also comes from multiple demands of different sizes. Assigning a ...
0
votes
0answers
14 views

How to calculate reduced cost in min cost flow networks for residual links?

I am constructing a min-cost flow network that represents a bipartite graph with cost and capacity constraints. To solve, that, I am using successive shortest path algorithms augmented with potential ...
5
votes
2answers
87 views

What is the name of this digraph created from other digraphs?

Let $D_1, D_2, ..., D_n$ be digraphs of various sizes and let $C$ be a diagraph with $n$ vertices $\{1,...,n\}$. Construct a new digraph, $D$, whose vertex set is $V(D) = V(D_1) \cup \cdots \cup V(D_n)...
0
votes
0answers
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 ...
2
votes
1answer
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 ...
5
votes
1answer
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 ...
1
vote
1answer
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 ...
5
votes
1answer
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) ...
4
votes
3answers
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 ...
12
votes
2answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
34 views

Cayley's tree formula proof

I want to prove Cayley's tree formula that The number of distinct trees of order $n$ with a specified vertex set is $n^{n-2}$ using the fact that the number of trees on the set of $n$ vertices $\{1,2,....
1
vote
1answer
47 views

Four-Colour Theorem Inquiry with handmade graph

I recently came across the 4-color theorem and tried to see if it worked with all maps just for fun, although I know it has been proved by mathematician much smarter than me. I opened up Microsoft ...
1
vote
1answer
31 views

The largest independent set in a graph and its set of $k$-subsets

I am working on the following exercise: Let $G := (V,E)$ be a graph. Consider $G^\prime := (V^\prime,E^\prime)$ with $V^\prime := \{ k \text{-subsets of } V \}$ and $E^\prime := \{(S_1,S_2) \mid S_1 \...
1
vote
1answer
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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$ ...
-1
votes
1answer
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 ...
0
votes
0answers
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 ...
0
votes
2answers
54 views

Number of subgraphs in $P_n$

Fix an integer $n \geq 1$. Suppose that $a_n$ denotes the number of subgraphs in $P_n$. Here $P_n$ denotes the graph with vertices $\{1,2, \dots,n-1, n\}$ and edges $\{j,j+1\}$, for all $1 \leq j \leq ...
0
votes
1answer
36 views

proving that If $G$ has at least $\frac{(n-1)(n-2)}{2}+1$ Edges then it's connected

I'm having some trouble with the following question: Let $G$ be a simple graph $n$ vertices and with at least $$\frac{(n-1)(n-2)}{2}+1$$ Edges. Prove that $G$ is Connected. I tried with some ...
0
votes
0answers
17 views

traffic assignment

Here are $m$ cities $C_1,\cdots,C_m$. The road connecting $V_i$ and $V_j$ is denoted as $E(i,j)$. Now there are $n$ trains $T_1,\cdots,T_n$. For each train $T_i$, it corresponds to two parameters: $...
2
votes
1answer
41 views

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 ...

1
2 3 4 5
430