Exams › GATE › Technical

The line graph L(G) of a simple graph G is defined as follows: • There is exactly one vertex v(e) in L(G) for each edge e in G. • For any two edges e and e' in G, L(G) has an edge between v(e) and v(e'), if and only if e and e' are incident with the same vertex in G. Which of the following statements is/are TRUE? (P) The line graph of a cycle is a cycle. (Q) The line graph of a clique is a clique. (R) The line graph of a planar graph is planar. (S) The line graph of a tree is a tree.

1. P only
2. P and R only
3. R only
4. P, Q and S only

Correct answer: P only

Solution

The statement P is true because the line graph of a cycle retains the cyclic structure, where each edge corresponds to a vertex in the line graph, and edges in the original cycle connect these vertices in a cyclic manner. The other statements do not hold true universally for their respective graph types.

Related GATE Technical questions

• The truth table X Y f(X,Y) 0 0 0 0 1 0 1 0 1 1 1 1 represents the Boolean function
• The decimal value 0.5 in IEEE single precision floating point representation has
• A process executes the code fork(); fork(); fork(); The total number of child processes created is
• The protocol data unit (PDU) for the application layer in the Internet stack is
• Which of the following problems are decidable? 1) Does a given program ever produce an output? 2) If L is a context-free language, then is L̄ also context-free? 3) If L is a regular language, then is L̄ also regular? 4) If L is a recursive language, then is L̄ also recursive?
• A binary operation ⊕ on a set of integers is defined as x ⊕ y = x² × y². Which one of the following statements is TRUE about ⊕?

⚔️ Practice GATE Technical free + battle 1v1 →