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
1answer
18 views

Shortest Path Length as mathematical function/expression

I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities. The degree of any node should be at least 3. The shortest path length ...
1
vote
0answers
37 views

Which directed graphs correspond to “algebraic” diagrams?

Any diagram for which the question of commutativity make sence is a directed graph, but not any directed graph make the question meaningful. $\require{AMScd}$ \begin{CD} A @>>> B @. A ...
0
votes
0answers
30 views

Basic Question on Cut in a Weighted Undirected Connected Graph

Background: I am a newbie to graph theory, specially in "graph cut". Please don't be too technical and fast. Thank you. Suppose I have a weighted undirected connected graph G=(V,E). I have a variable ...
0
votes
0answers
27 views

Application of Havel- Hakami Theorem [on hold]

Definition :Given a sequence $d_1 \geq d_2 \geq \cdots \geq d_n$ called graphical if it is degree of a possible graph. need a proof of the question below. Question : The above sequence is graphical ...
2
votes
1answer
41 views

Finding a path in a graph by its hash value

Assume there is a graph $G = (V, E)$ and a hash function $H: V^n \rightarrow \{0,1\}^m$. Given a path $p = (v_1, v_2, ..., v_n)$ from the graph $G$, compute its hash value $H(p) = h_p$. Question: ...
-2
votes
0answers
32 views

combinatorial nullstellensatz [on hold]

I was wondering if there is any trick for selecting the polynomial in Combinatorial Nullstellensatz method by Alon. This could be a powerful tool provided we choose right polynomial.
1
vote
0answers
69 views

Optimal allocation in network

Given a network (N,g). We want to analyse specializaton matters. Nodes are individuals, and they can product goods and services just like in our usual economy. Individuals can be consumers too. This ...
1
vote
0answers
22 views

Graph Theory: Find optimal subgraph that contains a certain node and a fixed number of nodes

I have a connected graph $G$ and a real-valued function $f$ on sub-graphs $G' \subseteq G$. Given a node $n \in G$ and a positive integer $s$, I am looking for the connected subgraph $G' \subseteq G$ ...
1
vote
0answers
76 views

How coefficients from finite field can form ring of polynomials?

Let us consider a graph $G(V,E),$ where $V$ is the set of nodes and $E$ is the set of edges. $\mathbf{x}=[X_1,\ldots,X_r]$ are symbols multicast by source to $|T|$ sink nodes. Symbols are from ...
2
votes
1answer
89 views

Simple connected plane graph G and its dual graph G*; if G is isomorphic to G*, then G is not bipartite?

Let $G$ be a simple connected plane graph where $v>2$, and $G^*$ is its dual graph. Prove that if $G$ is isomorphic to $G^*$, then $G$ is not bipartite. I know that $G$'s number of faces is ...
1
vote
0answers
36 views

what are these kind of graphs called in graph theory ?

Suppose the graph $G$ (here, we assume this graph is self-looped, i.e., each vertex is connected to itself) satisfies the following condition. For each vertex $v$ in $V(G)$, there is another vertex ...
1
vote
2answers
33 views

Find the total number of matchings in a complete graph with even vertices

I am trying to solve questions from a Walk through combinatorics.., I came across this proof which I was unable prove: Determine the number of perfect matchings for a graph with 2n vertices. I don't ...
1
vote
0answers
13 views

Directed Acyclic Graph - root and leaf node terminology

I have found conflicting terminology regarding how to label nodes in directed acyclic graphs. Specifically, I am looking for a definition of root and leaf nodes (preferably something to cite). For ...
-2
votes
0answers
23 views

LS Set Problem in Graph Theory [on hold]

It would be helpful if anyone please help me understand the concept of LS Set. I couldn't even understand how I could make use of LS Set in case of Social Computing Techniques.
0
votes
2answers
32 views

Maximal clique problem

I understood what clique is all the nodes of the sub graph have to be connected to each other. In the following figure, it says that the maximal clique is {1,2,3,4,5}. But as per the definition of ...
0
votes
0answers
27 views

All-pairs top-k min-cost flow paths

I am using a directed multigraph to model network flow. For example: Associated with each edge is: a cost of sending flow down that edge (red) a maximum capacity which the amount of flow sent ...
1
vote
1answer
30 views

Is there an efficient way to iterate vertex-transitive graphs?

For fixed number of vertices $n$, I want to iterate through all vertex-transitive simple graphs to check for some properties. A nice way to find vertex-transitive graphs is to iterate binary vectors ...
1
vote
1answer
49 views

What are the topics that must be covered in a beginning graph theory course? [on hold]

Good day to everyone. It will be my first time to make a syllabus on elementary graph theory. My question will be: What are the topics that must be covered in a beginning graph theory course? Also ...
0
votes
0answers
25 views

Question about Eulerian Circuits and Graph Connectedness

I read a theorem in a Graph Theory Introductory text. It says "If a pseudograph G has an Eulerian Circuit, then it is connected and every vertex of the graph G has even degree." Is it necessary that ...
1
vote
0answers
16 views

Sequential information discovery in minimum number of steps when some items have information about other items

There are N items, say three: call them A B and C. For each item, there is an associated bit (0 or 1) and there is a prior probability that the bit is 1, call them p(A), p(B) and p(C). There is some ...
1
vote
1answer
29 views

Drawing simple graphs from the degree of three vertices

I've just been introduced to graph theory in my discrete math class and I would like to see if my work and understanding of the topic is correct. Since there are many different terms and terminology ...
4
votes
0answers
45 views

Terminology in graph theory

Let $G$ be a finite graph with the following property: For any vertex $a$ and edge $\{b, c\}$ of $G$, there is an edge connecting them: there is one of $\{a,b\}$ or $\{a, c\}$ in $G$. Is there ...
1
vote
2answers
44 views

Proving that any connected graph has a vertex whose removal results in a connected graph

I want to prove that: for any simple, connected graph there is at least one node whose removal results in a connected graph. Here is my proof: Suppose that a graph $G$ is simple connected graph with ...
1
vote
0answers
15 views

Multigraphic Degree Sequences

Given a degree sequence $\{d_1,d_2,\ldots,d_n\}$, can I determine in polynomial time in $n$ whether this sequence is multigraphic AND can be realized by a connected multigraph? Looking at this ...
0
votes
0answers
9 views

k-way graph partitioning with bounded size constraint

A typical $k$-way graph partitioning problem is to partition a weighted graph into $k$ components, with the constraint that all $k$ components have the same size. However, if we drop the same size ...
2
votes
1answer
35 views

Vertex Reconstruction Conjecture For Asymmetric Graphs

Simple question: (a) Is it known whether all graphs G having trivial aut(G) are vertex reconstructible, and (b) what is the proof if it exists?
1
vote
1answer
28 views

What do you call a graph where the vertices are signed?

Let $G = (V, E)$ be a graph, and $f: V \to \{1,-1\}$ be a function assigning a sign to each vertex. What is this system $(G, f)$ called? In my current research, we've been using "oriented graph" ...
1
vote
1answer
25 views

Countability of the set of weighted graphs

Could you help me find the solution for this problem that consists in finding out wether the set of all weighted and finite graph is countable of not? As a reminder, a weighter graph can be seen as a ...
3
votes
1answer
32 views

Hopf algebra of graphs

Let $B$ be the set of isomorphism classes of finite graphs. Let $V$ be the $k$-vector space freely generated by $B$. I have heard that $V$ carries the structure of a Hopf algebra, and would like to ...
3
votes
0answers
28 views

Which graph with an automorphism group isomorphic to the quaternion group $Q_8$ minimizes $|V|+3|E|$?

In Symmetries of partial Latin squares, it is shown that for any graph $\Gamma=(V,E)$ with automorphism group $G$, there is a partial Latin square with $|V|+3|E|+49$ filled cells whose autotopism ...
0
votes
0answers
18 views

Displaying a graph with minimum overlapping edges

Context I am developing UI for a skill web for a mobile game. Each skill may have requirements from other skills, or sometimes no requirement at all. The problem The description above is ...
4
votes
1answer
33 views

Cubic Planar Graphs have $2^m-1$ Hamilton Cycles

I looked at the symmetric difference of hamilton cycle (HC) in cubic planar graphs and found that, together with the empty graph, they build a subgroup of the abelian group $\Omega$ of symmetric ...
1
vote
0answers
53 views

An extremal coloring problem

Is it true that there is $c\in\big[\frac{n}2,n+1\big]\cap\Bbb Z$ such that following holds if you assign single color to each edge of complete graph $K_n$: If $c$ colors are used in total, then ...
2
votes
1answer
31 views

Property of maximum matching

Let $G=(V,E)$ be a graph with no perfect matching. Then there exists a vertex v such that every incident edge is part of a maximum matching. I'm not sure how to prove this. How can every edge that ...
0
votes
1answer
57 views

how many ziplines between two buildings? [closed]

There are two buildings facing each other, each 5 stories high. How many ways can Kevin string ziplines between the buildings so that: (a) each zipline starts and ends in the middle of a floor. (b) ...
2
votes
2answers
55 views

how can I proof that a graph with 2n vertices is bipartite

If I have a graph without triangels 2n vertices and n^2 edges is it a bipartite graph? I couldn't find a counter example.
2
votes
1answer
36 views

Planar graph and number of faces of certain degree

Let G be a 4 regular connected planar graph (with a planar embedding), where all faces are either degree 3 or degree 4. Then determine the number of faces of degree 3. Also, now suppose that every ...
2
votes
2answers
39 views

Size of a maximum matching of a complete multipartite graph?

Let $G=(V,E)$ be a complete multipartite graph on even number of vertices, with $V(G) = X_1\cup X_2\cup\ldots\cup X_k$, let $n_i := |X_i|$, and suppose $n_1\le n_2\le \ldots\le n_k$. The problem I am ...
1
vote
0answers
61 views

Graph Theory number of handshakes of couples

This is an Olympiad question which I now know the answer to, but I am a bit unsatisfied with it. So maybe someone can shed some light: Question: $5$ couples go to a party. Each person shakes the ...
2
votes
1answer
48 views

The Adjacency Matrix of Symmetric Differences of any Subset of Faces has an Eigenvalue of $2$…?

Assume a planar graph $G$ and let's call its faces $f_k\in F$. The adjacency matrix of any face $f_k$ has an eigenvalue of $2$, since it's a $2$-regular graph, i.e. a cycle. I want to show that the ...
0
votes
0answers
18 views

Probability of random walk visit in nonameanable graphs

Consider a vertex-transitive nonameanable graph. Consider a site $x$ having a graph distance $d$ from the origin and let $X(n)$ be a random walk starting from $x$. Is there a general upper bound as a ...
4
votes
2answers
61 views

Minimal edge cut

Suppose that $C$ is a minimal edge cut of a graph $G=(V,E)$ is it possible that the removal of $C$ can split $G$ into three components? I ask this because i'm reading a proof which states that it's ...
0
votes
1answer
40 views

how to define this directed graph satisfying these conditions?

I want to know the definition of a type of directed graph that satisfies these conditions: 1) this is a directed graph; 2) there is a directed spanning tree in this graph; 3) there is not any ...
0
votes
1answer
66 views

How many vertices for non-isomorphic graphs?

I started drawing planar, cubic, bipartite graphs consisting of faces with 4 or 6 Vertices only. I found that 6 4-faces are sufficient to do that. The smallest graph is a planar drawing of the cube. ...
1
vote
1answer
228 views

Connected, planar, 3-colorable graph with every face of degree 3 has an Eulerian circuit

I am trying to prove that: If G is a connected graph where every face has a degree of 3 and is 3 colourable then there exists and Euler tour. This is what I have done: For a graph to have an ...
0
votes
0answers
38 views

Graph Theory:Folkman Graph

I want to prove that Folkman graph is edge transitive but not vertex transitive, and I don't know how can I start to prove, any help would be great thanks.
2
votes
0answers
27 views

An evenly divided $k$ coloring of an $(n,d,\lambda)$ graph leaves one vertex adjacent to all $k$ colors, given $k\lambda \leq d$.

(This is problem 9.2 from Alon and Spencer's The Probabilistic Method) Let $G = (V,E)$ be an $(n,d,\lambda)$-graph, suppose $n$ is divisible by $k$, and let $C:V \to \{1,2,\ldots,k\}$ be a ...
0
votes
0answers
14 views

Graph embeddings for informational networks

Say we have a fabric of computers (or anything that communicates) all talking to each other in the structure of a graph. If we have a lot of them, we can treat this graph as an approximation to a ...
0
votes
1answer
43 views

Diameter of random graph.

Basically I was given a random graph with fixed probability and I need to prove that the diameter of the random graph is asymptotically 2. See the following picture for the detail of the question. ...
3
votes
1answer
37 views

A problem on counting sub-graphs

How many distinct sub-graphs of a complete graph of $n$ labelled vertices are there, such that the sub-graph is a spanning tree connecting all the vertices and the degree of no vertex is more than ...