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

A succinct proof that the given graphs (red $K_n$ drawn cyclically, plus blue $2$-paths between closest vertices) have dihedral automorphism groups?

Take the complete graph $K_n$ ($n \geq 3$), on the red-colored vertex set $\mathbb{Z}_n$, say, and add a blue-colored $2$-path between each pair of vertices $v$, and $v+1$, we get a sequence of graphs ...
3
votes
1answer
19 views

Graph Theory: How quickly will triadic closure create a complete graph?

Imagine we are given a graph $G$ comprised of nodes $N$ and edges $E$. Assume the graph is connected (i.e. there exists a path connecting any pair of nodes). We can then iteratively update this ...
5
votes
0answers
42 views

Maximum leaf number of an $m \times n$ grid graph?

Are there any results regarding the maximum leaf number of an $m \times n$ two-dimensional grid graph? Either a closed form, or a table of values for small $m$ and $n$?
0
votes
0answers
17 views

How to find connected components in a weighted graph using edge weight as a criterion? [on hold]

How to connected components in a weighted undirected graph using edge weight as a criterion factor? Please see the following two examples: Example 1 Example 2 I need the connected components whose ...
0
votes
0answers
13 views

Optimization problem shortest path distance and critical node detection problem (interdiction).

I am trying to formulate this optimization problem, max $d_{ij}$ where $d_{ij}$ is the shortest distance between active nodes i and j. However my problem is connecting my decision variable with the ...
2
votes
0answers
20 views

Cycle triplets: A beats B beats C beats A. Minimum and maximum number of triplets for round-robin tournament of $2n+1$ teams? (contest question)

From the 2006 Canada National Olympiad: Consider a round-robin tournament with $2n + 1$ teams, where each team plays each other team exactly once. We say that three teams $X, Y\text{ and }Z$, ...
2
votes
1answer
34 views

Mixed strategy problem - game theory

I have a basic doubt in a question of game theory. Assume that in a $2$ player game the mixed strategy profile $((a,b,0),(c,d,0))$ is a mixed strategy NE. Does the indifference condition in a mixed ...
0
votes
0answers
34 views

Maximum number of edges without perfect matching

Let $G=(V,E)$ where $|V| = 2n $ , I had to find the maximum number of edges in G , such that G won't have perfect matching. I found the answer ($(2n-1) \choose 2$, we can see it is tight by taking ...
3
votes
0answers
28 views

What is this graph theory measurement called?

I am reading a scientific paper that measures the "relatedness" $s_{AB}$ of two (not necessarily connected) subgraphs of a connected graph with the formula $$ s_{AB} = d_{AB} - \dfrac{d_{AA} + ...
0
votes
0answers
14 views

What does $M_{uv}^l$ represent?

Let $M$ be any non negative square matrix. What does $M_{uv}^l$ represent? $M_{uv}^l$: $uv$ entry of $M^l$. (When $A$ is adjacency matrix of a graph, then $A_{uv}^l$ is number of walks of length $l$ ...
0
votes
1answer
18 views

Representing all pairs shortest path in a graph with a matrix

Given a graph $G(n,E)$ where $n$ is the number of nodes and $E$ represents the edges. Is there a way to represent or transform this into a matrix containing all the shortest paths between two pairs ...
4
votes
3answers
51 views

Prove a graph $(V,E)$ with $d$-maximal degree let $k=d/2+1$ can be decomposed as $V=V_1 \cup\cdots \cup V_k$ where each $V_i$ is a loopless graph

I tried looking at a vertex v with the maximal degree, that is $d(v)=d$ and started looking at it's neighbours $$N(v):=\{u\mid (u,v) \in E\}$$ therefore $|N(v)|=d$, now between every two vertice ...
0
votes
0answers
28 views

Plotting Distance Constrained Points on a Plane

Does anybody know of some algorithmic way to tell if it is possible to plot a set of distance constrained points on a cartesian plane. Or, better still, a method to determine the minimum number of ...
2
votes
0answers
27 views

Eigenvalues of the product of two “incidence” matrices

I am trying to solve the following problem. Let the following incidence matrix of an undirected graph with four nodes $$ B = \begin{bmatrix}1 & 0 & -1 & 0 & 0 \\ -1 & 1 & 0 ...
3
votes
1answer
78 views

k! perfect matches

Let $G=($ $ A \cup B $ , $E$ $)$ be a bipartite graph with perfect matching. Denote $|A| = n$. Prove that if every vertex in A has degree $\geq$ $k$ then G has at least $k!$ perfect matches. ...
1
vote
1answer
46 views

Graph Isomorphism of Complete Graph.

what Is the complexity(computational complexity) of graph isomorphism of 1.Complete graphs($K_n$) and 2.Utility graphs (Complete bipartite graphs ,$K_{n,n}$)? is it in polynomial ? Looks ...
1
vote
1answer
42 views

A question about combinatorial commutative diagrams.

In the comments of this question the directed graphs that can appear as commutative diagrams are axiomatized: A graph is a combinatorial commutative diagram iff it's nonempty and such that any ...
0
votes
1answer
29 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 ...
2
votes
1answer
74 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
29 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
42 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
33 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
78 views

Optimal allocation in network

We want to analyse specialization matters in a given network (N,g). Nodes represent individuals that can produce goods and services (just like in our usual economy) and that can be consumers too. ...
1
vote
0answers
23 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
81 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
91 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
44 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
34 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
15 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 [closed]

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
33 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
28 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
52 views

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

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
26 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
18 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
34 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
16 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
53 views
+350

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
26 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
36 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
31 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
19 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
37 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
54 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 ...