$2$-polarity and algorithmic aspects of polarity variants on cograph superclasses [PDF]
Discrete Mathematics & Theoretical Computer ScienceA graph $G$ is said to be an $(s, k)$-polar graph if its vertex set admits a partition $(A, B)$ such that $A$ and $B$ induce, respectively, a complete $s$-partite graph and the disjoint union of at most $k$ complete graphs.
Fernando Esteban Contreras-Mendoza +1 more
doaj +1 more source
The metric dimension and metric independence of a graph [PDF]
, 2001 A vertex x of a graph G resolves two vertices u and v of G if the distance from x to u does not equal the distance from x to v. A set S of vertices of G is a resolving set for G if every two distinct vertices of G are resolved by some vertex of S. The
Currie, James, Oellerman, Ortrud R.
core
Recognition of chordal graphs and cographs which are Cover-Incomparability graphs [PDF]
Discrete Mathematics & Theoretical Computer ScienceCover-Incomparability graphs (C-I graphs) are an interesting class of graphs from posets. A C-I graph is a graph from a poset $P=(V,\le)$ with vertex set $V$, and the edge-set is the union of edge sets of the cover graph and the incomparability graph of ...
Arun Anil, Manoj Changat
doaj +1 more source
The Algorithmic Complexity of Bondage and Reinforcement Problems in bipartite graphs [PDF]
, 2014 Let $G=(V,E)$ be a graph. A subset $D\subseteq V$ is a dominating set if every vertex not in $D$ is adjacent to a vertex in $D$. The domination number of $G$, denoted by $\gamma(G)$, is the smallest cardinality of a dominating set of $G$.
Hu, Fu-Tao, Sohn, Moo Young
core
Complexity of graphs generated by wheel graph and their asymptotic limits
Journal of the Egyptian Mathematical Society, 2017 The literature is very rich with works deal with the enumerating the spanning trees in any graph G since the pioneer Kirchhoff (1847). Generally, the number of spanning trees in a graph can be acquired by directly calculating an associated determinant ...
S.N. Daoud
doaj
A linear algorithm for obtaining the Laplacian eigenvalues of a cograph
Special MatricesIn this article, we give an O(n)O\left(n) time and space algorithm for obtaining the Laplacian eigenvalues of a cograph. This approach is more efficient as there is no need to directly compute the eigenvalues of Laplacian matrix related to this class of ...
Chen Guantao, Tura Fernando C.
doaj +1 more source
The Markov chain tree theorem and the state reduction algorithm in commutative semirings [PDF]
, 2013 We extend the Markov chain tree theorem to general commutative semirings, and we generalize the state reduction algorithm to commutative semifields. This leads to a new universal algorithm, whose prototype is the state reduction algorithm which computes ...
Gursoy, Buket Benek +3 more
core
Directed paths with few or many colors in colored directed graphs [PDF]
, 2000 Given a graph $D=(V(D),A(D))$ and a coloring of $D$, not necessarily a proper coloring of either the arcs or the vertices of $D$, we consider the complexity of finding a path of $D$ from a given vertex $s$ to another given vertex $t$ with as few ...
Broersma, H.J., Li, X., Zhang, S.
core +1 more source
Algorithmic releases on spanning trees of Jahangir graphs
, 2017 In this paper algebraic and combinatorial properties and a computation of the number of the spanning trees are developed for a Jahangir graph.Comment: 17 pages, 4 ...
Imbesi, Maurizio +2 more
core
Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number. [PDF]
Algorithmica, 2023 Misra P, Saurabh S, Sharma R, Zehavi M.
europepmc +1 more source