Zobrazeno 1 - 10
of 13 833
pro vyhledávání: '"Computer Science::Discrete Mathematics"'
Publikováno v:
Journal of Computer and System Sciences. 137:50-65
Given access to the hypergraph through a subset query oracle in the query model, we give sublinear time algorithms for Hitting-Set with almost tight parameterized query complexity. In parameterized query complexity, we estimate the number of queries
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::11e70c5d5284c0ea1e653e88613db462
https://doi.org/10.1016/j.jcss.2023.02.002
https://doi.org/10.1016/j.jcss.2023.02.002
Autor:
Chudnovsky, Maria, Seymour, Paul
Publikováno v:
Journal of Combinatorial Theory, Series B. 161:331-381
A {\em hole} in a graph is an induced subgraph which is a cycle of length at least four. A hole is called {\em even} if it has an even number of vertices. An {\em even-hole-free} graph is a graph with no even holes. A vertex of a graph is {\em bisimp
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::059a994d08939e458199872e949ca314
https://doi.org/10.1016/j.jctb.2023.02.009
https://doi.org/10.1016/j.jctb.2023.02.009
Publikováno v:
Journal of Algebra. 626:1-38
In 2017, Giudici, Li and the third author constructed the first known family of vertex-primitive $2$-arc-transitive digraphs of valency at least $2$. The smallest digraph in this family admits $\mathrm{PSL}_3(49)$ acting $2$-arc-transitively with ver
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::fdfa056cc721b743898203d81c506d21
https://doi.org/10.1016/j.jalgebra.2023.02.028
https://doi.org/10.1016/j.jalgebra.2023.02.028
Autor:
Haviv, Ishay, Parnas, Michal
Publikováno v:
Journal of Computer and System Sciences. 134:73-86
A $0,1$ matrix is said to be regular if all of its rows and columns have the same number of ones. We prove that for infinitely many integers $k$, there exists a square regular $0,1$ matrix with binary rank $k$, such that the Boolean rank of its compl
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::112d78c1b1baea7558cf33a86394465e
https://doi.org/10.1016/j.jcss.2023.01.005
https://doi.org/10.1016/j.jcss.2023.01.005
Autor:
Anirban Banerjee, Samiron Parui
Publikováno v:
Linear Algebra and its Applications. 667:97-132
Here we introduce connectivity operators, namely, diffusion operators, general Laplacian operators, and general adjacency operators for hypergraphs. These operators are generalisations of some conventional notions of apparently different connectivity
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::58474c1486545cdbba391ed7e761250f
https://doi.org/10.1016/j.laa.2023.03.001
https://doi.org/10.1016/j.laa.2023.03.001
Publikováno v:
Linear Algebra and its Applications. 664:126-146
In this article, we extend the notion of the Laplacian spread to simple directed graphs (digraphs) using the restricted numerical range. First, we provide Laplacian spread values for several families of digraphs. Then, we prove sharp upper bounds on
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::e66875273a842b5f3267ed981fb751b2
https://doi.org/10.1016/j.laa.2023.01.016
https://doi.org/10.1016/j.laa.2023.01.016
Publikováno v:
Journal of Combinatorial Theory, Series B. 160:1-14
Let $G$ be a bridgeless cubic graph. The Berge--Fulkerson Conjecture (1970s) states that $G$ admits a list of six perfect matchings such that each edge of $G$ belongs to exactly two of these perfect matchings. If answered in the affirmative, two othe
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::da5b3b41a28bf140eb9998a63b094984
https://doi.org/10.1016/j.jctb.2022.12.003
https://doi.org/10.1016/j.jctb.2022.12.003
Autor:
Thomas, Robin, Yoo, Youngho
Publikováno v:
Journal of Combinatorial Theory, Series B. 160:114-143
It is known that $A$-paths of length $0$ mod $m$ satisfy the Erd\H{o}s-P\'osa property if $m=2$ or $m=4$, but not if $m > 4$ is composite. We show that if $p$ is prime, then $A$-paths of length $0$ mod $p$ satisfy the Erd\H{o}s-P\'osa property. More
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::311a0e7266e7b8995f1a2f35bf4fa806
https://doi.org/10.1016/j.jctb.2022.12.007
https://doi.org/10.1016/j.jctb.2022.12.007
Publikováno v:
International Journal of Algebra and Computation. 33:481-498
Given a simple undirected graph $G$ there is a simplicial complex $\mathrm{Ind}(G)$, called the independence complex, whose faces correspond to the independent sets of $G$. This is a well studied concept because it provides a fertile ground for inter
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::1cfc68050ac1625c9bde69a709a31151
https://doi.org/10.1142/s0218196723500236
https://doi.org/10.1142/s0218196723500236
Publikováno v:
THEORETICAL COMPUTER SCIENCE
The diamond is the graph obtained by removing an edge from the complete graph on 4 vertices. A graph is ($P_6$, diamond)-free if it contains no induced subgraph isomorphic to a six-vertex path or a diamond. In this paper we show that the chromatic nu
Externí odkaz:
https://explore.openaire.eu/search/publication?articleId=doi_dedup___::ac522ec22e2cbcbf843bf75eab7fc7b7
https://doi.org/10.1016/j.tcs.2022.11.020
https://doi.org/10.1016/j.tcs.2022.11.020