Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new user$mathcal{B}$-partitions, application to determinant and permanent of graphs
304
0
0.0
(
0
)
Added by
Ranveer Singh
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
Let $G$ be a graph(directed or undirected) having $k$ number of blocks. A $mathcal{B}$-partition of $G$ is a partition into $k$ vertex-disjoint subgraph $(hat{B_1},hat{B_1},hdots,hat{B_k})$ such that $hat{B}_i$ is induced subgraph of $B_i$ for $i=1,2,hdots,k.$ The terms $prod_{i=1}^{k}det(hat{B}_i), prod_{i=1}^{k}text{per}(hat{B}_i)$ are det-summands and per-summands, respectively, corresponding to the $mathcal{B}$-partition. The determinant and permanent of a graph having no loops on its cut-vertices is equal to summation of det-summands and per-summands, respectively, corresponding to all possible $mathcal{B}$-partitions. Thus, in this paper we calculate determinant and permanent of some graphs, which include block graph with negatives cliques, signed unicyclic graph, mix complete graph, negative mix complete graph, and star mix block graphs.
rate research
Read More
We view the determinant and permanent as functions on directed weighted graphs and introduce their analogues for the undirected graphs. We prove that the task of computing the undirected determinants as well as permanents for planar graphs, whose vertices have degree at most 4, is #P-complete. In the case of planar graphs whose vertices have degree at most 3, the computation of the undirected determinant remains #P-complete while the permanent can be reduced to the FKT algorithm, and therefore is polynomial. The undirected permanent is a Holant problem and its complexity can be deduced from the existing literature. The concept of the undirected determinant is new. Its introduction is motivated by the formal resemblance to the directed determinant, a property that may inspire generalizations of some of the many algorithms which compute the latter. For a sizable class of planar 3-regular graphs, we are able to compute the undirected determinant in polynomial time.
A circle graph is a graph in which the adjacency of vertices can be represented as the intersection of chords of a circle. The problem of calculating the chromatic number is known to be NP-complete, even on circle graphs. In this paper, we propose a new integer linear programming formulation for a coloring problem on circle graphs. We also show that the linear relaxation problem of our formulation finds the fractional chromatic number of a given circle graph. As a byproduct, our formulation gives a polynomial-sized linear programming formulation for calculating the fractional chromatic number of a circle graph. We also extend our result to a formulation for a capacitated stowage stack minimization problem.
The question whether a partition $mathcal{P}$ and a hierarchy $mathcal{H}$ or a tree-like split system $mathfrak{S}$ are compatible naturally arises in a wide range of classification problems. In the setting of phylogenetic trees, one asks whether the sets of $mathcal{P}$ coincide with leaf sets of connected components obtained by deleting some edges from the tree $T$ that represents $mathcal{H}$ or $mathfrak{S}$, respectively. More generally, we ask whether a refinement $T^*$ of $T$ exists such that $T^*$ and $mathcal{P}$ are compatible. We report several characterizations for (refinements of) hierarchies and split systems that are compatible with (sets of) partitions. In addition, we provide a linear-time algorithm to check whether refinements of trees and a given partition are compatible. The latter problem becomes NP-complete but fixed-parameter tractable if a set of partitions is considered instead of a single partition. We finally explore the close relationship of the concept of compatibility and so-called Fitch maps.
Motivated by recent computational models for redistricting and detection of gerrymandering, we study the following problem on graph partitions. Given a graph $G$ and an integer $kgeq 1$, a $k$-district map of $G$ is a partition of $V(G)$ into $k$ nonempty subsets, called districts, each of which induces a connected subgraph of $G$. A switch is an operation that modifies a $k$-district map by reassigning a subset of vertices from one district to an adjacent district; a 1-switch is a switch that moves a single vertex. We study the connectivity of the configuration space of all $k$-district maps of a graph $G$ under 1-switch operations. We give a combinatorial characterization for the connectedness of this space that can be tested efficiently. We prove that it is NP-complete to decide whether there exists a sequence of 1-switches that takes a given $k$-district map into another; and NP-hard to find the shortest such sequence (even if a sequence of polynomial length is known to exist). We also present efficient algorithms for computing a sequence of 1-switches that takes a given $k$-district map into another when the space is connected, and show that these algorithms perform a worst-case optimal number of switches up to constant factors.
There is a digraph corresponding to every square matrix over $mathbb{C}$. We generate a recurrence relation using the Laplace expansion to calculate the characteristic, and permanent polynomials of a square matrix. Solving this recurrence relation, we found that the characteristic, and permanent polynomials can be calculated in terms of characteristic, and permanent polynomials of some specific induced subdigraphs of blocks in the digraph, respectively. Interestingly, these induced subdigraphs are vertex-disjoint and they partition the digraph. Similar to the characteristic, and permanent polynomials; the determinant, and permanent can also be calculated. Therefore, this article provides a combinatorial meaning of these useful quantities of the matrix theory. We conclude this article with a number of open problems which may be attempted for further research in this direction.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
