A note on kernels and solutions in digraphs
For given nonnegative integers k,s an upper bound on the minimum number of vertices of a strongly connected digraph with exactly k kernels and s solutions is presented.
A note on (k,l)-kernels in B-products of graphs
B-products of graphs and their generalizations were introduced in [4]. We determined the parameters k, l of (k,l)-kernels in generalized B-products of graphs. These results are generalizations of theorems from [2].
A note on k-uniform self-complementary hypergraphs of given order
We prove that a k-uniform self-complementary hypergraph of order n exists, if and only if is even.
A note on line colorings of cubic graphs
A note on line graphs
A note on linear discrepancy.
A note on link graphs
A Note on Longest Paths in Circular Arc Graphs
As observed by Rautenbach and Sereni [SIAM J. Discrete Math. 28 (2014) 335-341] there is a gap in the proof of the theorem of Balister et al. [Combin. Probab. Comput. 13 (2004) 311-317], which states that the intersection of all longest paths in a connected circular arc graph is nonempty. In this paper we close this gap.
A note on major sequences and external activity in trees.
A note on majorization transforms and Ryser’s algorithm
The notion of a transfer (or T -transform) is central in the theory of majorization. For instance, it lies behind the characterization of majorization in terms of doubly stochastic matrices. We introduce a new type of majorization transfer called L-transforms and prove some of its properties. Moreover, we discuss how L-transforms give a new perspective on Ryser’s algorithm for constructing (0; 1)-matrices with given row and column sums.
A note on maximal common subgraphs of the Dirac's family of graphs
Let ⁿ be a given set of unlabeled simple graphs of order n. A maximal common subgraph of the graphs of the set ⁿ is a common subgraph F of order n of each member of ⁿ, that is not properly contained in any larger common subgraph of each member of ⁿ. By well-known Dirac’s Theorem, the Dirac’s family ⁿ of the graphs of order n and minimum degree δ ≥ [n/2] has a maximal common subgraph containing Cₙ. In this note we study the problem of determining all maximal common subgraphs of the Dirac’s family...
A note on maximal -degenerate graphs
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a 3-approximation...
A note on maximum independent sets and minimum clique partitions in unit disk graphs and penny graphs: complexity and approximation
A unit disk graph is the intersection graph of a family of unit disks in the plane. If the disks do not overlap, it is also a unit coin graph or penny graph. It is known that finding a maximum independent set in a unit disk graph is a NP-hard problem. In this work we extend this result to penny graphs. Furthermore, we prove that finding a minimum clique partition in a penny graph is also NP-hard, and present two linear-time approximation algorithms for the computation of clique partitions: a 3-approximation...
A note on minimally 3-connected graphs
If G is a minimally 3-connected graph and C is a double cover of the set of edges of G by irreducible walks, then |E(G)| ≥ 2| C| - 2.
A note on minimum rank and maximum nullity of sign patterns.
A note on Möbius inversion over power set lattices
In this paper, we establish a theorem on Möbius inversion over power set lattices which strongly generalizes an early result of Whitney on graph colouring.
A note on Narayana triangles and related polynomials, Riordan arrays, and MIMO capacity calculations.
A note on naturally embedded ternary trees.
A Note on Neighbor Expanded Sum Distinguishing Index
A total k-coloring of a graph G is a coloring of vertices and edges of G using colors of the set [k] = {1, . . . , k}. These colors can be used to distinguish the vertices of G. There are many possibilities of such a distinction. In this paper, we consider the sum of colors on incident edges and adjacent vertices.