Search

The clique transversal problem is a critical concept in graph theory, focused on identifying a minimum subset of vertices that intersects all maximal cliques in a graph. This problem and its variations—such as the k-fold clique, { k } -clique, minus clique, and signed clique transversal problems—have received significant interest due to their theoretical importance and practical applications. This paper examines the k-fold clique, { k } -clique, minus clique, and signed clique transversal problems on distance-hereditary graphs. Known for their distinctive structural properties, distance hereditary graphs provide an ideal framework for studying these problem variants. By exploring these issues in the context of distance-hereditary graphs, this research enhances the understanding of the computational challenges and the potential for developing efficient algorithms to address these problems. [ABSTRACT FROM AUTHOR]

The transversal number Τ (H) of a hypergraph H is the minimum number of vertices that intersect every edge of H. A 6-uniform hypergraph has all edges of size 6. On 10 November 2000 Tuza and Vestergaard [Discuss. Math. Graph Theory, 22 (2002), pp. 199-210] conjectured that if H is a 3-regular 6-uniform hypergraph of order n, then Τ(H) < 1/4n. In this paper we prove this conjecture, which has become known as the Tuza-Vestergaard conjecture. [ABSTRACT FROM AUTHOR]

Copyright of Innovacion Educativa is the property of Universidad de Santiago de Compostela, Servicio de Publicaciones and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)

For a subgraph $G$ of the blow-up of a graph $F$ , we let $\delta ^*(G)$ be the smallest minimum degree over all of the bipartite subgraphs of $G$ induced by pairs of parts that correspond to edges of $F$. Johansson proved that if $G$ is a spanning subgraph of the blow-up of $C_3$ with parts of size $n$ and $\delta ^*(G) \ge \frac{2}{3}n + \sqrt{n}$ , then $G$ contains $n$ vertex disjoint triangles, and presented the following conjecture of Häggkvist. If $G$ is a spanning subgraph of the blow-up of $C_k$ with parts of size $n$ and $\delta ^*(G) \ge \left(1 + \frac 1k\right)\frac n2 + 1$ , then $G$ contains $n$ vertex disjoint copies of $C_k$ such that each $C_k$ intersects each of the $k$ parts exactly once. A similar conjecture was also made by Fischer and the case $k=3$ was proved for large $n$ by Magyar and Martin. In this paper, we prove the conjecture of Häggkvist asymptotically. We also pose a conjecture which generalises this result by allowing the minimum degree conditions in each bipartite subgraph induced by pairs of parts of $G$ to vary. We support this new conjecture by proving the triangle case. This result generalises Johannson's result asymptotically. [ABSTRACT FROM AUTHOR]

We study the complexity of graph modification problems with respect to homomorphism-based colouring properties of edge-coloured graphs. A homomorphism from an edge-coloured graph G to an edge-coloured graph H is a vertex-mapping from G to H that preserves adjacencies and edge-colours. We consider the property of having a homomorphism to a fixed edge-coloured graph H, which generalises the classic vertex-colourability property. The question we are interested in is the following: given an edge-coloured graph G, can we perform k graph operations so that the resulting graph admits a homomorphism to H? The operations we consider are vertex-deletion, edge-deletion and switching (an operation that permutes the colours of the edges incident to a given vertex). Switching plays an important role in the theory of signed graphs, that are 2-edge-coloured graphs whose colours are the signs + and −. We denote the corresponding problems (parameterized by k) by VD-H-Colouring, ED-H-Colouring and SW-H-Colouring. These problems generalise the extensively studied H-Colouring problem (where one has to decide if an input graph admits a homomorphism to a fixed target H). For 2-edge-coloured H, it is known that H-Colouring already captures the complexity of all fixed-target Constraint Satisfaction Problems. Our main focus is on the case where H is an edge-coloured graph with at most two vertices, a case that is already interesting since it includes standard problems such as Vertex Cover, Odd Cycle Transversal and Edge Bipartization. For such a graph H, we give a P/NP-complete complexity dichotomy for all three VD-H-Colouring, ED-H-Colouring and SW-H-Colouring problems. Then, we address their parameterized complexity. We show that all VD-H-Colouring and ED-H-Colouring problems for such H are FPT. This is in contrast with the fact that already for some H of order 3, unless P = NP, none of the three considered problems is in XP, since 3- Colouring is NP-complete. We show that the situation is different for SW-H-Colouring: there are three 2-edge-coloured graphs H of order 2 for which SW-H-Colouring is W[1]-hard, and assuming the ETH, admits no algorithm in time f (k) n o (k) for inputs of size n and for any computable function f. For the other cases, SW-H-Colouring is FPT. [ABSTRACT FROM AUTHOR]

A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number τ (H) of H is the minimum size of a transversal in H. A hypergraph H is 3-uniform if every edge of H has size 3. Let H be a 3-uniform hypergraph with n H vertices and m H edges. Tuza (Discrete Math 86:117–126, 1990) and Chvátal and McDiarmid (Combinatorica 12:19–26, 1992) showed that 4 τ (H) ≤ n H + m H . Chvátal and McDiarmid also showed that 6 τ (H) ≤ 2 n H + m H . The linear hypergraphs achieving equality in these bounds were characterized by the authors (Henning and Yeo in J Graph Theory 59:326–348, 2008; Discrete Math 313:959–966, 2013). In this paper, we show that these bounds can be improved if we impose some structural properties on H. We show that if H does not contain a subhypergraph isomorphic to the affine plane AG(2, 3) of order 3 with two vertices deleted, then 17 τ (H) ≤ 5 n H + 3 m H . The total domination number γ t (G) of a graph G is the minimum cardinality of a set S of vertices so that every vertex in G is adjacent to some vertex in S. It is known (Archdeacon et al. in J Graph Theory 46:207–210, 2004) that if G is a graph of order n with minimum degree at least 3, then γ t (G) ≤ 1 2 n , and that this bound is tight. As a consequence of our hypergraph results, we show that if G is a graph of order n with minimum degree at least 3 that contains no 4-cycles and no specified graph on 12 vertices as a subgraph, then γ t (G) ≤ 8 17 n . [ABSTRACT FROM AUTHOR]

In 1957 Hugo Steinhaus published an elementary, recreational problem concerning a configuration of rooks on the chessboard (Steinhaus in Matematyka, czasopismo dla nauczycieli 1:55, 1957). Over the last 60 years, this problem has achieved quite a peculiar status: apparently, it had two (both published) solutions—one short and elegant (Steinhaus in Sto zadań [One Hundred Problems], PWN, Warszawa, 1958), but (as it soon turned out) incorrect (Zadania konkursowe, Rozwiązania [Competition problems, Solutions]. Matematyka, Czasopismo dla nauczycieli 4-6:62-65, 1958); while the other (Zadania konkursowe, 1958) (Steinhaus in One Hundred Problems in Elementary Mathematics. Popular Lectures in Mathematics, Pergamon Press, Oxford and PWN, Warszawa, 1963)—known internationally, yet long and complex, so probably never read (except, perhaps, by its author) and never checked for its correctness. It was only in 2004 when a correct and short solution of the original Steinhaus' problem was found and published (Morawiec in Matematyka Czasopismo dla nauczycieli 2:46-50, 2004). The solution involved the well-known Hall's 'marriage' theorem (Wilson in Introduction to Graph Theory, Longman, Harlow, 1996, p. 113). Further investigation has shown that the connection between Steinhaus' problem and Hall's theorem runs deeper than the use of the latter in the solution of the former. In this paper we present the results of this investigation, by the way defining a simple but seemingly new class of special matchings (ibid.) in bipartite graphs (id., p. 18). [ABSTRACT FROM AUTHOR]

A subset T of vertices in a hypergraph H is a transversal if T has a nonempty intersection with every edge of H. The transversal number of H is the minimum size of a transversal in H. A subset S of vertices in a graph G with no isolated vertex, is a total dominating set if every vertex of G is adjacent to a vertex of S. The minimum cardinality of a total dominating set in G is the total domination number of G. In this paper, we obtain a new (improved) probabilistic upper bound for the transversal number of a hypergraph, and a new (improved) probabilistic upper bound for the total domination number of a graph. [ABSTRACT FROM AUTHOR]

The following question was raised by Tuza in 1990 and Erdős et al. in 1992: if every edge of an n‐vertex chordal graph G is contained in a clique of size at least four, does G have a clique transversal, i.e. a set of vertices meeting all nontrivial maximal cliques, of size at most n/4? We prove that every such graph G has a clique transversal of size at most 2(n−1)/7 if n≥5, which is the best possible bound. [ABSTRACT FROM AUTHOR]

Paul Erdős and László Lovász established by means of an example that there exists a maximal intersecting family of k -sets with ⌊ ( e − 1 ) k ! ⌋ blocks, where e is the base of natural logarithm. László Lovász conjectured that their example is best known example which has the maximum number of blocks. Later it was disproved. But the quest for such examples remain valid till this date. In this note we compute the transversal size of a certain series of intersecting families of k -sets, which is constructed over the Cyclic graph. It helps to provide an example of maximal intersecting family of k -sets with so many blocks and to present two worthwhile examples which disprove two special cases of one of the conjectures of Frankl et al. [ABSTRACT FROM AUTHOR]

Tuza’s Conjecture asserts that the minimum number τΔ′(G) of edges of a graph G whose deletion results in a triangle-free graph is at most 2 times the maximum number νΔ′(G) of edge-disjoint triangles of G. The complete graphs K4 and K5 show that the constant 2 would be best possible. Moreover, if true, the conjecture would be essentially tight even for K4-free graphs. In this paper, we consider several subclasses of K4-free graphs. We show that the constant 2 can be improved for them and we try to provide the optimal one. The classes we consider are of two kinds: graphs with edges in few triangles and graphs obtained by forbidding certain odd-wheels. We translate an approximate min-max relation for τΔ′(G) and νΔ′(G) into an equivalent one for the clique cover number and the independence number of the triangle graph of G and we provide θ-bounding functions for classes related to triangle graphs. In particular, we obtain optimal θ-bounding functions for the classes Free(K5,claw,diamond) and Free(P5,diamond,K2,3) and a χ-bounding function for the class (banner,odd-hole,K1,4¯). [ABSTRACT FROM AUTHOR]

We study the class of binary matroids without a P10-minor and find all internally 4-connected non-regular matroids in the class. [ABSTRACT FROM AUTHOR]

Multimatroids generalize matroids, delta-matroids, and isotropic systems, and transition polynomials of multimatroids subsume various polynomials for these latter combinatorial structures, such as the interlace polynomial and the Tutte–Martin polynomial. We prove evaluations of the Tutte–Martin polynomial of isotropic systems from Bouchet directly and more efficiently in the context of transition polynomials of multimatroids. Moreover, we generalize some related evaluations of the transition polynomial of 4-regular graphs from Jaeger to multimatroids. These evaluations are obtained in a uniform and matroid-theoretic way. We also translate the evaluations in terms of the interlace polynomial of graphs. Finally, we give an excluded-minor theorem for the class of binary tight 3-matroids (a subclass of multimatroids) based on the excluded-minor theorem for the class of binary delta-matroids from Bouchet. [ABSTRACT FROM AUTHOR]

We perform a systematic study in the computational complexity of the connected variant of three related transversal problems: Vertex Cover , Feedback Vertex Set , and Odd Cycle Transversal . Just like their original counterparts, these variants are NP -complete for general graphs. A graph G is H -free for some graph H if G contains no induced subgraph isomorphic to H . It is known that Connected Vertex Cover is NP -complete even for H -free graphs if H contains a claw or a cycle. We show that the two other connected variants also remain NP -complete if H contains a cycle or claw. In the remaining case H is a linear forest. We show that Connected Vertex Cover , Connected Feedback Vertex Set , and Connected Odd Cycle Transversal are polynomial-time solvable for s P 2 -free graphs for every constant s ≥ 1 . For proving these results we use known results on the price of connectivity for vertex cover, feedback vertex set, and odd cycle transversal. This is the first application of the price of connectivity that results in polynomial-time algorithms. [ABSTRACT FROM AUTHOR]

A d-interval hypergraph has d disjoint copies of the unit interval as its vertex set, and each edge is the union of d subintervals, one on each copy. Extending a classical result of Gallai on the case $$d=1$$ , Tardos and Kaiser used topological tools to bound the ratio between the transversal number and the matching number in such hypergraphs. We take a dual point of view, and bound the edge-covering number (namely the minimal number of edges covering the entire vertex set) in terms of a parameter expressing independence of systems of partitions of the d unit intervals. The main tool we use is an extension of the KKM theorem to products of simplices, due to Peleg. [ABSTRACT FROM AUTHOR]

Line graphs constitute a rich and well-studied class of graphs. In this paper, we focus on three different topics related to line graphs of subcubic triangle-free graphs. First, we show that any such graph G has an independent set of size at least 3 | V ( G ) | ∕ 10 , the bound being sharp. As an immediate consequence, we have that any subcubic triangle-free graph G , with n i vertices of degree i , has a matching of size at least 3 n 1 ∕ 20 + 3 n 2 ∕ 10 + 9 n 3 ∕ 20 . Then we provide several approximate min-max theorems relating cycle-transversals and cycle-packings of line graphs of subcubic triangle-free graphs. This enables us to prove Jones’ Conjecture for claw-free graphs with maximum degree 4 . Finally, we concentrate on the computational complexity of Feedback Vertex Set , Hamiltonian Cycle and Hamiltonian Path for subclasses of line graphs of subcubic triangle-free graphs. [ABSTRACT FROM AUTHOR]

A total dominating set of a graph G having non empty intersection with all the independent sets of maximum cardinality in G is an independent transversal total dominating set. The minimum cardinality of any independent transversal total dominating set is denoted by γ t t ( G ) . In this paper we introduce this concept and begin the study of its mathematical properties. Specifically, we prove that the complexity of the decision problem associated to the computation of the value of γ t t ( G ) is NP-complete, under the assumption that the independence number is known. Moreover, we present tight lower and upper bounds on γ t t ( G ) and give some realizability results in concordance with these bounds. For instance, we show that for any two positive integers a , b such that 2 ≤ a ≤ 2 b 3 there is a graph G of order b such that γ t t ( G ) = a . [ABSTRACT FROM AUTHOR]

We consider the size of the smallest set of vertices required to intersect every longest path in a chordal graph. Such sets are known as longest path transversals. We show that if ω (G) is the clique number of a chordal graph G , then there is a transversal of order at most 4 ⌈ ω (G) 5 ⌉. We also consider the analogous question for longest cycles, and show that if G is a 2-connected chordal graph then there is a transversal intersecting all longest cycles of order at most 2 ⌈ ω (G) 3 ⌉. [ABSTRACT FROM AUTHOR]

For a family of graphs F , an F -transversal of a graph G is a subset S ⊆ V ( G ) that intersects every subset of V ( G ) that induces a subgraph isomorphic to a graph in F . Let t F ( G ) be the minimum size of an F -transversal of G , and ct F ( G ) be the minimum size of an F -transversal of G that induces a connected graph. For a class of connected graphs G , we say that the price of connectivity of F -transversals is multiplicative if, for all G ∈ G , ct F ( G ) / t F ( G ) is bounded by a constant, and additive if ct F ( G ) − t F ( G ) is bounded by a constant. The price of connectivity is identical if t F ( G ) and ct F ( G ) are always equal and unbounded if ct F ( G ) cannot be bounded in terms of t F ( G ) . We study classes of graphs characterized by one forbidden induced subgraph H and F -transversals where F contains an infinite number of cycles and, possibly, also one or more anticycles or short paths. We determine exactly those classes of connected H -free graphs where the price of connectivity of these F -transversals is unbounded, multiplicative, additive, or identical. In particular, our tetrachotomies extend known results for the case when F is the family of all cycles. [ABSTRACT FROM AUTHOR]

A simple graph G = (V, E) is said to be r-regular if each vertex of G is of degree r. The vertex covering transversal domination number γ vct(G) is the minimum cardinality among all vertex covering transversal dominating sets of G. In this paper, we analyse this parameter on different kinds of regular graphs especially for Q n and H 3,n. Also we provide an upper bound for γ vct of a connected cubic graph of order n ≥ 8. Then we try to provide a more stronger relationship between γ and γ vct. [ABSTRACT FROM AUTHOR]