Some Variations of Perfect Graphs by Dettlaff Magda, Lemańska Magdalena, Semanišin Gabriel, Zuazua Rita

Subjects: “…k-path vertex cover…”
Get full text

A Note on Outer-Independent 2-Rainbow Domination in Graphs by Abel Cabrera-Martínez

Subjects: Get full text

Some Graph Polynomials of the Power Graph and its Supergraphs by Asma Hamzeh

Subjects: Get full text

Q-MeaMetaVC: An MVC Solver of a Large-Scale Graph Based on Membrane Evolutionary Algorithms by Chunmei Liao, Ping Guo, Jiaqi Gu, Qiuju Deng

Subjects: Get full text

Bounds on the Clique and the Independence Number for Certain Classes of Graphs by Valentin E. Brimkov, Reneta P. Barneva

Subjects: Get full text

Matching Number, Independence Number, and Covering Vertex Number of Γ(Zn) by Eman AbuHijleh, Mohammad Abudayah, Omar Alomari, Hasan Al-Ezeh

Subjects: Get full text

On the sum of signless Laplacian spectra of graphs by S. Pirzada, H.A. Ganie, A.M. Alghamdi

Subjects: Get full text

Application of an Extremal Result of Erdős and Gallai to the (n,k,t) Problem by Matt Noble, Peter Johnson, Dean Hoffman, Jessica McDonald

Subjects: “…vertex cover…”
Get full text

Defining the Minimum Security Baseline in a Multiple Security Standards Environment by Graph Theory Techniques by Dmitrij Olifer, Nikolaj Goranin, Antanas Cenys, Arnas Kaceniauskas, Justinas Janulevicius

Subjects: Get full text

Identify multiple seeds for influence maximization by statistical physics approach and multi-hop coverage by Fuxuan Liao, Yukio Hayashi

Subjects: Get full text

<i>k</i>-step Reachability Query Processing on Label-constrained Graph by DU Ming, XING Rui-ping, ZHOU Jun-feng, TAN Yu-ting

Subjects: “…label-constrained graph|<i>k</i>-step reachability query|2-hop index|vertex cover|graph theory…”
Get full text

Vertex sequences in graphs by Teresa W. Haynes, Stephen T. Hedetniemi

Subjects: Get full text

Layered Graphs: Applications and Algorithms by Bhadrachalam Chitturi, Srijith Balachander, Sandeep Satheesh, Krithic Puthiyoppil

Subjects: Get full text

Coloring and Guarding Arrangements by Prosenjit Bose, Jean Cardinal, Sébastien Collette, Ferran Hurtado, Matias Korman, Stefan Langerman, Perouz Taslakian

Subjects: Get full text

On Generalized Sierpiński Graphs by Rodríguez-Velázquez Juan Alberto, Rodríguez-Bazan Erick David, Estrada-Moreno Alejandro

Subjects: Get full text

Simultaneously dominating all spanning trees of a graph by Sebastian Johann, Sven O. Krumke, Manuel Streicher

“…We prove that on 2-connected graphs, a subset of the vertices dominates all spanning trees of the graph if and only if it is a vertex cover. Using this fact we present an exact algorithm that finds a simultaneous dominating set of minimum size using an oracle for finding a minimum vertex cover. …”
Get full text

Hardness and approximation of submodular minimum linear ordering problems by Farhadi, Majid, Gupta, Swati, Sun, Shengding, Tetali, Prasad, Wigal, Michael C.

“…We settle this question through non-trivial reductions from mininimum latency vertex cover and minimum sum vertex cover problems. We further propose a new combinatorial algorithm for approximating monotone submodular MLOP, using the theory of principal partitions. …”
Get full text

Combinatorial Dominance Guarantees for Heuristic Algorithms by Daniel Berend, Steven S. Skiena, Yochai Twitto

“…In this paper, we analyze several heuristics for $\textit{Vertex Cover}$, $\textit{Set Cover}$, and $\textit{Knapsack}$ for dominance bounds. …”
Get full text

Counting edge-injective homomorphisms and matchings on restricted graph classes by Curticapean, R, Dell, H, Roth, M

“…We show that edge-injective homomorphisms from a pattern graph H can be counted in polynomial time if H has bounded vertex-cover number after removing isolated edges. For hereditary classes H of pattern graphs, we complement this result: If the graphs in H have unbounded vertex-cover number even after deleting isolated edges, then counting edge-injective homomorphisms with patterns from H is #W[1]-hard. …”

Constant time algorithms in sparse graph model by Nguyen, Huy Ngoc, Ph. D. Massachusetts Institute of Technology

Get full text