Results 41 to 50 of about 1,423 (126)

On the Spectrum of Threshold Graphs

International Scholarly Research Notices, Volume 2011, Issue 1, 2011., 2011
The antiregular connected graph on r vertices is defined as the connected graph whose vertex degrees take the values of r − 1 distinct positive integers. We explore the spectrum of its adjacency matrix and show common properties with those of connected threshold graphs, having an equitable partition with a minimal number r of parts.
Irene Sciriha, Stephanie Farrugia, F. Ergun, P. Feinsilver, Y. Hou, S. Y. Song, N. I. Trinajstić   +6 more
wiley   +1 more source

Apex Graphs and Cographs

Theory and Applications of Graphs
A class G of graphs is called hereditary if it is closed under taking induced subgraphs. We denote by G^{apex} the class of graphs G that contain a vertex v such that G − v is in G.
Jagdeep Singh, Vaidy Sivaraman, Thomas Zaslavsky   +2 more
doaj   +1 more source

Odd chromatic number of graph classes

Journal of Graph Theory, Volume 108, Issue 4, Page 722-744, April 2025.
Abstract A graph is called odd (respectively, even) if every vertex has odd (respectively, even) degree. Gallai proved that every graph can be partitioned into two even induced subgraphs, or into an odd and an even induced subgraph. We refer to a partition into odd subgraphs as an odd colouring of G $G$.
Rémy Belmonte, Ararat Harutyunyan, Noleen Köhler, Nikolaos Melissinos   +3 more
wiley   +1 more source

An efficient g‐centroid location algorithm for cographs

International Journal of Mathematics and Mathematical Sciences, Volume 2005, Issue 9, Page 1405-1413, 2005., 2005
In 1998, Pandu Rangan et al. Proved that locating the g‐centroid for an arbitrary graph is 𝒩𝒫‐hard by reducing the problem of finding the maximum clique size of a graph to the g‐centroid location problem. They have also given an efficient polynomial time algorithm for locating the g‐centroid for maximal outerplanar graphs, Ptolemaic graphs, and split ...
V. Prakash
wiley   +1 more source

Designing classes’ interfaces for neural network graph model

Труды Института системного программирования РАН, 2019
An approach to testing artificial neural networks is described. The model of neural network is based on graph theory, and operations that are used in theoretical works devoted to graphs, trees, paths, cycles, and circuits.
Yuri Leonidovich Karpov, Irina Anatolievna Volkova, Alexey Alexandrovich Vylitok, Leonid Evgenievich Karpov, Yuri Gennadievich Smetanin   +4 more
doaj   +1 more source

The complexity of the perfect matching‐cut problem

Journal of Graph Theory, Volume 108, Issue 3, Page 432-462, March 2025.
Abstract PERFECT MATCHING‐CUT is the problem of deciding whether a graph has a perfect matching that contains an edge‐cut. We show that this problem is NP‐complete for planar graphs with maximum degree four, for planar graphs with girth five, for bipartite five‐regular graphs, for graphs of diameter three, and for bipartite graphs of diameter four.
Valentin Bouquet, Christophe Picouleau
wiley   +1 more source

CCSMR: A Combinatorial Category Space-Based Model for Recommendation

IEEE Access, 2019
Various side information has been exploited in recommender systems to help users finding items they prefer to alleviate data sparsity. Because item category can be used to view the user's preference in a high-level scope and an item can have more than ...
Chunjing Xiao, Kewen Xia, Leilei Sun, Cong Xie, Yuxiang Zhang   +4 more
doaj   +1 more source

On the Edge‐Density of the Brownian Co‐Graphon and Common Ancestors of Pairs in the CRT

Random Structures &Algorithms, Volume 66, Issue 1, January 2025.
ABSTRACT Bassino et al. have shown that uniform random co‐graphs (graphs without induced P4$$ {P}_4 $$) of size n$$ n $$ converge to a certain non‐deterministic graphon. The edge density of this graphon is a random variable Λ∈[0,1]$$ \boldsymbol{\Lambda} \in \left[0,1\right] $$ whose first moments have been computed by these authors.
Guillaume Chapuy
wiley   +1 more source

Data Reduction for Graph Coloring Problems

, 2013
This paper studies the kernelization complexity of graph coloring problems with respect to certain structural parameterizations of the input instances. We are interested in how well polynomial-time data reduction can provably shrink instances of coloring
Bart M.P. Jansen, Bodlaender, Bodlaender, Bodlaender, Bodlaender, Bodlaender, Brandstädt, Bruce, Cai, Chor, Dell, Downey, Fellows, Fellows, Fiala, Fomin, Fomin, Fortnow, Garey, Guo, Hoàng, Jansen, Knuth, Kobler, Kratochvíl, Lokshtanov, Marx, Marx, Stefan Kratsch, Tuza, Yap   +30 more
core   +1 more source

Scheduling on uniform machines with a conflict graph: complexity and resolution

International Transactions in Operational Research, Volume 31, Issue 2, Page 863-888, March 2024.
Abstract This paper deals with the problem of scheduling a set of unit‐time jobs on a set of uniform machines. The jobs are subject to conflict constraints modeled by a graph G called the conflict graph, in which adjacent jobs cannot be processed on a same machine.
Amin Mallek, Mourad Boudhar
wiley   +1 more source