GRAPHS AND COMBINATORICS, ISSN 0911-0119, 07/2019, Volume 35, Issue 4, pp. 921 - 931

Let k be a positive integer and let D be a digraph. A path partitionP of D is a set of vertex-disjoint paths which coversV(D). Its k-norm is defined as Sigma...

Coloring | MATHEMATICS | Berge's Conjecture | Aharoni | Path partition | Hartman | and Hoffman's Conjecture | Locally in-semicomplete digraphs | Olefins

Coloring | MATHEMATICS | Berge's Conjecture | Aharoni | Path partition | Hartman | and Hoffman's Conjecture | Locally in-semicomplete digraphs | Olefins

Journal Article

Graphs and Combinatorics, ISSN 0911-0119, 9/2016, Volume 32, Issue 5, pp. 1873 - 1879

A digraph is locally-in semicomplete if for every vertex of D its in-neighborhood induces a semicomplete digraph and it is locally semicomplete if for every...

05C20 | 05C75 | CKI-digraphs | Locally semicomplete digraphs | Mathematics | Engineering Design | Combinatorics | 05C69 | Kernel | MATHEMATICS | TOURNAMENTS

05C20 | 05C75 | CKI-digraphs | Locally semicomplete digraphs | Mathematics | Engineering Design | Combinatorics | 05C69 | Kernel | MATHEMATICS | TOURNAMENTS

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 11/2012, Volume 160, Issue 16-17, pp. 2491 - 2496

Let D be a hamiltonian digraph. A nonempty vertex set X⊆V(D) is called an H-force set of D if every X-cycle of D (i.e. a cycle of D containing all vertices of...

[formula omitted]-force number | Locally semicomplete digraphs | [formula omitted]-force set | H-force number | H-force set | MATHEMATICS, APPLIED

[formula omitted]-force number | Locally semicomplete digraphs | [formula omitted]-force set | H-force number | H-force set | MATHEMATICS, APPLIED

Journal Article

Discussiones Mathematicae Graph Theory, ISSN 1234-3099, 05/2018, Volume 38, Issue 2, pp. 477 - 490

Let = ( ) be a digraph; if there is at least one arc between every pair of distinct vertices of , then is a semicomplete digraph. A digraph is locally...

05C20 | Hamiltonian cycle | locally semicomplete digraph | arc-disjoint | Hamiltonian path | round decomposable | local tournament | Local tournament | Arc-disjoint | Locally semicomplete digraph | Round decomposable | MATHEMATICS | TOURNAMENTS

05C20 | Hamiltonian cycle | locally semicomplete digraph | arc-disjoint | Hamiltonian path | round decomposable | local tournament | Local tournament | Arc-disjoint | Locally semicomplete digraph | Round decomposable | MATHEMATICS | TOURNAMENTS

Journal Article

Graphs and Combinatorics, ISSN 0911-0119, 7/2019, Volume 35, Issue 4, pp. 921 - 931

Let k be a positive integer and let D be a digraph. A path partition $$\mathcal {P}$$ P of D is a set of vertex-disjoint paths which covers V(D). Its k -norm...

Coloring | Berge’s Conjecture | Mathematics | Engineering Design | Combinatorics | Path partition | Locally in-semicomplete digraphs | Aharoni, Hartman, and Hoffman’s Conjecture | Collection | Partitions | Graph theory | Apexes | Weight

Coloring | Berge’s Conjecture | Mathematics | Engineering Design | Combinatorics | Path partition | Locally in-semicomplete digraphs | Aharoni, Hartman, and Hoffman’s Conjecture | Collection | Partitions | Graph theory | Apexes | Weight

Journal Article

6.
Full Text
Arc‐Disjoint In‐ and Out‐Branchings With the Same Root in Locally Semicomplete Digraphs

Journal of Graph Theory, ISSN 0364-9024, 12/2014, Volume 77, Issue 4, pp. 278 - 298

Deciding whether a digraph contains a pair of arc‐disjoint in‐ and out‐branchings rooted at a specified vertex is a well‐known NP‐complete problem (as proved...

arc‐disjoint in‐ and out‐branchings | structure of locally semicomplete digraphs | polynomial time algorithm | Locally semicomplete digraph | arc‐contraction | Polynomial time algorithm | Structure of locally semicomplete digraphs | Arc-contraction | Arc-disjoint in- And out-branchings

arc‐disjoint in‐ and out‐branchings | structure of locally semicomplete digraphs | polynomial time algorithm | Locally semicomplete digraph | arc‐contraction | Polynomial time algorithm | Structure of locally semicomplete digraphs | Arc-contraction | Arc-disjoint in- And out-branchings

Journal Article

Discrete Mathematics, ISSN 0012-365X, 06/2012, Volume 312, Issue 11, pp. 1883 - 1891

Arc-locally semicomplete digraphs were introduced by Bang-Jensen as a common generalization of both semicomplete and semicomplete bipartite digraphs in 1993....

Arc-locally semicomplete digraph | Directed graph | Arc-local tournament | Generalization of tournaments | Independent set of vertices | MATHEMATICS | TOURNAMENTS | Mathematical analysis | Graph theory | Classification

Arc-locally semicomplete digraph | Directed graph | Arc-local tournament | Generalization of tournaments | Independent set of vertices | MATHEMATICS | TOURNAMENTS | Mathematical analysis | Graph theory | Classification

Journal Article

Journal of Combinatorial Theory, Series B, ISSN 0095-8956, 05/2012, Volume 102, Issue 3, pp. 701 - 714

We prove that the arc set of every 2-arc-strong locally semicomplete digraph D=(V,A) which is not the second power of an even cycle can be partitioned into two...

Decomposition into strong spanning subdigraphs | Connectivity | Hamiltonian cycle | Structure of locally semicomplete digraphs | Strong spanning subdigraph | Locally semicomplete digraph | MATHEMATICS | TOURNAMENTS

Decomposition into strong spanning subdigraphs | Connectivity | Hamiltonian cycle | Structure of locally semicomplete digraphs | Strong spanning subdigraph | Locally semicomplete digraph | MATHEMATICS | TOURNAMENTS

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 06/2017, Volume 85, Issue 2, pp. 545 - 567

The k‐linkage problem is as follows: given a digraph D=(V,A) and a collection of k terminal pairs (s1,t1),…,(sk,tk) such that all these vertices are distinct;...

polynomial algorithm | disjoint paths | k‐linkage problem | quasi‐transitive digraph | (round‐)decomposable digraphs | locally semicomplete digraph | (round-)decomposable digraphs | k-linkage problem | quasi-transitive digraph | MATHEMATICS | QUASI-TRANSITIVE DIGRAPHS | TOURNAMENTS | LOCALLY SEMICOMPLETE DIGRAPHS

polynomial algorithm | disjoint paths | k‐linkage problem | quasi‐transitive digraph | (round‐)decomposable digraphs | locally semicomplete digraph | (round-)decomposable digraphs | k-linkage problem | quasi-transitive digraph | MATHEMATICS | QUASI-TRANSITIVE DIGRAPHS | TOURNAMENTS | LOCALLY SEMICOMPLETE DIGRAPHS

Journal Article

Discrete Mathematics, ISSN 0012-365X, 2009, Volume 309, Issue 23, pp. 6555 - 6562

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x , y , every in-neighbor of x and every in-neighbor of y either are adjacent or...

Arc-locally semicomplete digraphs | Semicomplete digraphs | Semicomplete bipartite digraphs | Digraphs | MATHEMATICS | PATHS

Arc-locally semicomplete digraphs | Semicomplete digraphs | Semicomplete bipartite digraphs | Digraphs | MATHEMATICS | PATHS

Journal Article

Discrete Mathematics, ISSN 0012-365X, 02/2011, Volume 311, Issue 4, pp. 282 - 288

A digraph is arc-locally in-semicomplete if for any pair of adjacent vertices x,y, every in-neighbor of x and every in-neighbor of y either are adjacent or are...

Arc-locally in-semicomplete digraphs | Non-augmentable paths | Quasi-arc-transitive digraphs | Independent sets | Digraphs | MATHEMATICS | Mathematical analysis | Graph theory

Arc-locally in-semicomplete digraphs | Non-augmentable paths | Quasi-arc-transitive digraphs | Independent sets | Digraphs | MATHEMATICS | Mathematical analysis | Graph theory

Journal Article

Discrete Mathematics, ISSN 0012-365X, 2010, Volume 310, Issue 20, pp. 2675 - 2684

In this paper we establish a dichotomy theorem for the complexity of homomorphisms to fixed locally semicomplete digraphs. It is also shown that the same...

Locally semicomplete digraphs | Digraph homomorphism | Polynomial algorithm | NP-completeness | Complexity | MATHEMATICS | TOURNAMENTS | Computer science | Algorithms | Homomorphisms | Theorems | Lists | Mathematical analysis | Colouring | Dichotomies

Locally semicomplete digraphs | Digraph homomorphism | Polynomial algorithm | NP-completeness | Complexity | MATHEMATICS | TOURNAMENTS | Computer science | Algorithms | Homomorphisms | Theorems | Lists | Mathematical analysis | Colouring | Dichotomies

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 2009, Volume 157, Issue 11, pp. 2536 - 2540

We point out mistakes in two papers previously published in Discrete Applied Mathematics, dealing with highly strongly connected spanning local tournaments in...

Connectivity in digraphs | Local tournament | Semicomplete digraph | Tournament | Locally semicomplete digraph | MATHEMATICS, APPLIED

Connectivity in digraphs | Local tournament | Semicomplete digraph | Tournament | Locally semicomplete digraph | MATHEMATICS, APPLIED

Journal Article

Electronic Notes in Discrete Mathematics, ISSN 1571-0653, 2009, Volume 34, pp. 59 - 61

Journal Article

Journal of Graph Theory, ISSN 0364-9024, 09/2014, Volume 77, Issue 2, pp. 89 - 110

We prove that the weak k‐linkage problem is polynomial for every fixed k for totally Φ‐decomposable digraphs, under appropriate hypothesis on Φ. We then apply...

locally semicomplete digraph | cut‐width | decomposable digraph | quasi‐transitive digraph | arc‐disjoint paths | modular partition | weak linkages | cut-width | arc-disjoint paths | quasi-transitive digraph | MATHEMATICS

locally semicomplete digraph | cut‐width | decomposable digraph | quasi‐transitive digraph | arc‐disjoint paths | modular partition | weak linkages | cut-width | arc-disjoint paths | quasi-transitive digraph | MATHEMATICS

Journal Article

Discrete Applied Mathematics, ISSN 0166-218X, 2005, Volume 146, Issue 3, pp. 245 - 256

It is well known that the problem of deciding whether a given digraph has a k-cycle factor for some constant k (i.e. a collection of k disjoint cycles that...

2-Cycle factor | Polynomial algorithm | Semicomplete digraph | Locally semicomplete digraph | Complementary cycles | MATHEMATICS, APPLIED | locally semicomplete digraph | TOURNAMENTS | 2-cycle factor | semicomplete digraph | polynomial algorithm | complementary cycles

2-Cycle factor | Polynomial algorithm | Semicomplete digraph | Locally semicomplete digraph | Complementary cycles | MATHEMATICS, APPLIED | locally semicomplete digraph | TOURNAMENTS | 2-cycle factor | semicomplete digraph | polynomial algorithm | complementary cycles

Journal Article

Algorithmica, ISSN 0178-4617, 10/2016, Volume 76, Issue 2, pp. 320 - 343

In the Directed Feedback Arc (Vertex) Set problem, we are given a digraph D with vertex set V(D) and arcs set A(D) and a positive integer k, and the question...

Feedback arc set | Feedback vertex set | Theory of Computation | Kernels | Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Decomposable digraph | Locally semicomplete digraph | Computer Science | Bounded independence number | Quasi-transitive digraph | Algorithm Analysis and Problem Complexity | Parameterized complexity | SEMICOMPLETE DIGRAPHS | MATHEMATICS, APPLIED | NP | VERTEX SET | GRAPHS | COMPUTER SCIENCE, SOFTWARE ENGINEERING | ARC SET | BIPARTITE TOURNAMENTS | Computer science

Feedback arc set | Feedback vertex set | Theory of Computation | Kernels | Computer Systems Organization and Communication Networks | Data Structures, Cryptology and Information Theory | Algorithms | Mathematics of Computing | Decomposable digraph | Locally semicomplete digraph | Computer Science | Bounded independence number | Quasi-transitive digraph | Algorithm Analysis and Problem Complexity | Parameterized complexity | SEMICOMPLETE DIGRAPHS | MATHEMATICS, APPLIED | NP | VERTEX SET | GRAPHS | COMPUTER SCIENCE, SOFTWARE ENGINEERING | ARC SET | BIPARTITE TOURNAMENTS | Computer science

Journal Article

Graphs and Combinatorics, ISSN 0911-0119, 5/2019, Volume 35, Issue 3, pp. 669 - 675

Kernel is an important topic in digraphs. A digraph such that every proper induced subdigraph has a kernel is said to be critical kernel imperfect (CKI, for...

Arc-locally in-semicomplete digraph | 05C20 | Generalization of bipartite tournaments | CKI-digraph | Mathematics | Engineering Design | Combinatorics | 3-Anti-quasi-transitive digraph | 05C69 | Kernel | 3-Quasi-transitive digraph | MATHEMATICS | Kernels | Asymmetry | Graph theory

Arc-locally in-semicomplete digraph | 05C20 | Generalization of bipartite tournaments | CKI-digraph | Mathematics | Engineering Design | Combinatorics | 3-Anti-quasi-transitive digraph | 05C69 | Kernel | 3-Quasi-transitive digraph | MATHEMATICS | Kernels | Asymmetry | Graph theory

Journal Article

IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, ISSN 0916-8508, 2014, Volume E97-A, Issue 6, pp. 1192 - 1199

A twin dominating set of a digraph D is a subset S of vertices if, for every vertex u is not an element of 5, there are vertices x, y is an element of S such...

Locally semicomplete digraphs | Twin domination | Round digraphs | Digraphs | digraphs | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | DE-BRUIJN | COMPUTER SCIENCE, INFORMATION SYSTEMS | locally semicomplete digraphs | twin domination | round digraphs | ENGINEERING, ELECTRICAL & ELECTRONIC

Locally semicomplete digraphs | Twin domination | Round digraphs | Digraphs | digraphs | COMPUTER SCIENCE, HARDWARE & ARCHITECTURE | DE-BRUIJN | COMPUTER SCIENCE, INFORMATION SYSTEMS | locally semicomplete digraphs | twin domination | round digraphs | ENGINEERING, ELECTRICAL & ELECTRONIC

Journal Article

Discrete Mathematics, ISSN 0012-365X, 2010, Volume 310, Issue 19, pp. 2495 - 2498

In this paper, D = ( V ( D ) , A ( D ) ) denotes a loopless directed graph (digraph) with at most one arc from u to v for every pair of vertices u and v of V (...

Arc-locally semicomplete digraphs | Hamiltonian digraphs | 3-quasi-transitive digraphs | Generalization of tournaments | MATHEMATICS | Mathematical analysis | Graphs

Arc-locally semicomplete digraphs | Hamiltonian digraphs | 3-quasi-transitive digraphs | Generalization of tournaments | MATHEMATICS | Mathematical analysis | Graphs

Journal Article

No results were found for your search.

Cannot display more than 1000 results, please narrow the terms of your search.