In this paper, we characterize line graphs and total graphs that are hinge-free, i.e., there is no triple of vertices x, y, z such that the distance between y and z increases after x is removed. ...Based on our characterizations, we show that given a graph G with n vertices and m edges, determining its line graph and total graph to be hinge-free can be solved in O(n + m) time. Moreover, characterizations of hinge-free iterated line graphs and total graphs are also discussed.
Full text
Available for:
BFBNIB, NMLJ, NUK, PNG, UL, UM, UPUK
We investigate the enumerative aspects of various classes of perfect graphs like cographs, split graphs, trivially perfect graphs and threshold graphs. For subclasses of permutation graphs like ...cographs and threshold graphs we also determine the number of permutations
π of {1,2,…,
n} such that the permutation graph
G
π belongs to that class. We establish an interesting bijection between permutations whose permutation graphs are cographs (
P
4-free graphs) and permutations that are obtainable using an
output-restricted deque (Knuth, Art of Computer Programming, Vol I, Fundamental Algorithms) and thereby enumerate such permutations. We also prove that the asymptotic number of permutations of {1,2,…,
n} whose permutation graphs are split graphs is
Θ(4
n/
n
)
. We also introduce a new class of graphs called
C
5-split graphs, characterize and enumerate them.
C
5-split graphs form a superclass of split graphs and are not necessarily perfect. All the classes of graphs that we enumerate have a finite family of small forbidden induced subgraphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
Distance-hereditary graphs are graphs in which every two vertices have the same distance in every connected induced subgraph containing them. This paper studies distance-hereditary graphs from an ...algorithmic viewpoint. In particular, we present linear-time algorithms for finding a minimum weighted connected dominating set and a minimum vertex-weighted Steiner tree in a distance-hereditary graph. Both problems are
N P
-complete in general graphs.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
A subset S ¿ V in a graph G = ( V , E ) is a k -quasiperfect dominating set (for k = 1) if every vertex not in S is adjacent to at least one and at most k vertices in S . The cardinality of a minimum ...k -quasiperfect dominating set in G is denoted by ¿ 1 k ( G ). Those sets were first introduced by Chellali et al. (2013) as a generalization of the perfect domination concept and allow us to construct a decreasing chain of quasiperfect dominating numbers n = ¿ 11 ( G ) = ¿ 12 ( G ) = ... = ¿ 1 ¿ ( G ) = ¿ ( G ) in order to indicate how far is G from being perfectly dominated. In this paper we study properties, existence and realization of graphs for which the chain is short, that is, ¿ 12 ( G ) = ¿ ( G ). Among them, one can find cographs, claw-free graphs and graphs with extremal values of ¿ ( G ).
Full text
Available for:
BFBNIB, NMLJ, NUK, PNG, UL, UM, UPUK
257.
P_4-Colorings and P_4-Bipartite Graphs Hoàng, Chinh T.; Le, Van Bang
Discrete mathematics and theoretical computer science,
01/2001, Volume:
4 no. 2, Issue:
2
Journal Article
Peer reviewed
Open access
A vertex partition of a graph into disjoint subsets V_is is said to be a P_4-free coloring if each color class V_i induces a subgraph without chordless path on four vertices (denoted by P_4). ...Examples of P_4-free 2-colorable graphs (also called P_4-bipartite graphs) include parity graphs and graphs with ''few'' P_4s like P_4-reducible and P_4-sparse graphs. We prove that, given k≥ 2, \emphP_4-Free k-Colorability is NP-complete even for comparability graphs, and for P_5-free graphs. We then discuss the recognition, perfection and the Strong Perfect Graph Conjecture (SPGC) for P_4-bipartite graphs with special P_4-structure. In particular, we show that the SPGC is true for P_4-bipartite graphs with one P_3-free color class meeting every P_4 at a midpoint.
A set
P
of disjoint paths in a graph
G is called a
(complete) path cover of
G if every vertex of
G belongs to one of the paths in
P
. A path cover of any subgraph of
G is called a
partial path cover ...of
G. For fixed
k>0, a
k-blanket of graph
G is a partial path cover
P
of
G, consisting of exactly
k paths, that maximizes the size of the subgraph covered by
P
. A
k-core of graph
G is a partial path cover
P
of
G, consisting of exactly
k paths, that minimizes the sum, over all vertices
v of
G, of the distance of
v to its closest path in
P
. The problems of finding a
k-blanket or a
k-core (for fixed
k) of an arbitrary graph
G as well as the dual minimum-path-cover problem (find a path cover of minimum size) are all NP-hard. A linear-time algorithm is known (C.J. Chang and D. Kuo, SIAM J. Discrete Math. 9 (1996) 309–316) for the minimum-path-cover problem on cographs (graphs that can be constructed from a collection of isolated vertices by union and complement operations). However, prior to this paper, polynomial-time algorithms for the
k -core problem were known only for trees — and even then for
k = 1, 2 only (Becker and Perl, Discrete Appl. Math. 11 (1985) 103–113; Morgan and Slater, SIAM J. Appl. Math. 37 (1979) 539–560). In this paper, we introduce a variant of a minimum path cover, called a
perfect path cover. We show that every cograph has a perfect path cover, and we exploit this to obtain an
O(
m +
n
log
n)-time algorithm for finding, for any arbitrary
k, a
k-blanket or a
k-core of a arbitrary cograph on
n vertices and
m edges.
Full text
Available for:
GEOZS, IJS, IMTLJ, KILJ, KISLJ, NLZOH, NUK, OILJ, PNG, SAZU, SBCE, SBJE, UILJ, UL, UM, UPCLJ, UPUK, ZAGLJ, ZRSKP
The concept of a checking test is of prime interest to the study of a variant of exact identification problem, in which the learner is given a hint about the unknown object. A graph F is said to be a ...checking test for a co graph G iff for any other co graph H there exists an edge in F distinguishing G and H, that is, contained in exactly one of the graphs G and H. It is known that for any co graph G there exists a unique irredundant checking test, the number of edges in which is called the checking test complexity of G. We show that almost all co graphs on n vertices have relatively small checking test complexity of O(n log n). Using this result, we obtain an upper bound on the checking test complexity of almost all read-once Boolean functions over the basis of disjunction and parity functions.
PDF
