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.
A note on neighbour-distinguishing regular graphs total-weighting.
A note on nested sums.
A Note on Non-Dominating Set Partitions in Graphs
A set S of vertices of a graph G is a dominating set if every vertex not in S is adjacent to a vertex of S and is a total dominating set if every vertex of G is adjacent to a vertex of S. The cardinality of a minimum dominating (total dominating) set of G is called the domination (total domination) number. A set that does not dominate (totally dominate) G is called a non-dominating (non-total dominating) set of G. A partition of the vertices of G into non-dominating (non-total dominating) sets is...
A note on nonisomorphic Steiner quadruple systems
A note on odd cycle-complete graph Ramsey numbers.
A note on on-line ranking number of graphs
A -ranking of a graph is a mapping such that each path with endvertices of the same colour contains an internal vertex with colour greater than . The ranking number of a graph is the smallest positive integer admitting a -ranking of . In the on-line version of the problem, the vertices of arrive one by one in an arbitrary order, and only the edges of the induced graph are known when the colour for the vertex has to be chosen. The on-line ranking number of a graph is the smallest...
A note on optimality conditions for dual problems to the traveling salesman problem
A note on outerplanarity of product graphs